Count 1 s present in a range of indices [ L , R ] in a given array | Java program to implement the above approach ; Function to find the size of the array if the array initially contains a single element ; Base case ; P / 2 -> findSize ( N / 2 ) P % 2 -> 1 P / 2 -> findSize ( N / 2 ) ; Function to return the count of 1 s in the range [ L , R ] ; Base Case ; PART 1 -> N / 2 [ 1 , Siz_M ] ; Update the right end point of the range to min ( Siz_M , R ) ; PART 2 -> N % 2 [ SizM + 1 , Siz_M + 1 ] ; PART 3 -> N / 2 [ SizM + 2 , 2 * Siz_M - 1 ] Same as PART 1 Property of Symmetricity Shift the coordinates according to PART 1 Subtract ( Siz_M + 1 ) from both L , R ; Driver Code ; Input ; Counts the number of 1 's in  the range [L, R]
import java . util . * ; class GFG { static int findSize ( int N ) { if ( N == 0 ) return 1 ; if ( N == 1 ) return 1 ; int Size = 2 * findSize ( N / 2 ) + 1 ; return Size ; } static int CountOnes ( int N , int L , int R ) { if ( L > R ) { return 0 ; } if ( N <= 1 ) { return N ; } int ret = 0 ; int M = N / 2 ; int Siz_M = findSize ( M ) ; if ( L <= Siz_M ) { ret += CountOnes ( N / 2 , L , Math . min ( Siz_M , R ) ) ; } if ( L <= Siz_M + 1 && Siz_M + 1 <= R ) { ret += N % 2 ; } if ( Siz_M + 1 < R ) { ret += CountOnes ( N / 2 , Math . max ( 1 , L - Siz_M - 1 ) , R - Siz_M - 1 ) ; } return ret ; } public static void main ( String [ ] args ) { int N = 7 , L = 2 , R = 5 ; System . out . println ( CountOnes ( N , L , R ) ) ; } }