Number of substrings with odd decimal value in a binary string | function to count number of substrings with odd decimal representation ; auxiliary array to store count of 1 's  before ith index ; store count of 1 's  before i-th index ; variable to store answer ; traverse the string reversely to calculate number of odd substrings before i - th index ; Driver code
< ? php function countSubstr ( $ s ) { $ n = strlen ( $ s ) ; $ auxArr = array ( ) ; if ( $ s [ 0 ] == '1' ) $ auxArr [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { if ( $ s [ $ i ] == '1' ) $ auxArr [ $ i ] = $ auxArr [ $ i - 1 ] + 1 ; else $ auxArr [ $ i ] = $ auxArr [ $ i - 1 ] ; } $ count = 0 ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) if ( $ s [ $ i ] == '1' ) $ count += $ auxArr [ $ i ] ; return $ count ; } $ s = "1101" ; echo countSubstr ( $ s ) ; ? >