Given a string S consisting of only 1’s and 0’s, find the number of substrings which start and end both in 1.
You need to find number of pairs of 1.
Find total number of 1’s in the given string. Let suppose that the total number of 1’s in the string is n , then the answer is (n*(n+1))/2.
Let’s suppose that the n 1’s in the string occur at x1 , x2, … , xn position in the string then all substring starting from xi and ending at xj are taken, so total possible ways in taking it is (n*(n+1))/2
solve(string s) int n = 0 for ( i = 0 ; i< s.size() ; i++) if s[i] == '1' n++ return (n*(n+1))/2
O(N), You just need a single pass of the string.