count number of substrings that start and end with 1

For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.

Ans

a) Count the number of 1’s. Let the count of 1’s be m.
b) Return m(m-1)/2

Apti

               1 
             1   1
             2   1
          1  2   1   1
       1  1  1   2   2   1

What is the next line?

Answer

LZ algorithm

Next line is pairs (count, digit) for sequence of digits in previous line.

3 1 2 2 1 1