Do you know any number you can easily make with a combination of a power of 2 ?

[ 1, 2, 4, 8, 16, 32, 64, 128, 256]

for example

candidates eligible to make 27

27 = [ 16, 8, 4, 2, 1] why not bigger than 16 obvious power of 2 must be less than or equal to number

now the question is what actually set of candidates?

we just adding from highest to lowest and if anyone exceeding 27 let’s mark it as incompatible

16 = 16 < 27 , 16 + 8 = 24 < 27, 24 +4 > 27 ( 4 is not compatible). , 24+2 < 27

required set 27 = [16, 24, 2, 1]

sum from L to R + power of 2 ≤ number then power of 2 is required candidate and include in sum from L to R else not

find number of ones — [1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

assuming number of ones = n

if we are able to find combination of power of two for making n then we are done right ?

let assume biggest power of 2 = 64

one at 64th position ? NO

one at 32th position ? NO

one at 16th position ? YES n =16

one at 8th position ? YES n = 24

one at 4th position ? YES n=28 but 28 not possible as 0 is at 28th position so discard 4

one at 2nd position ? YES n=26

one at 1st position ? YES n=27

stop here

27 = [ 16, 8, 2, 1]

how it works

we want to make 27 from combination of power of 2. we have strong reasons to reject or accept every power of two.

totalOnes(binArr) {
 pow2 = 64
 ans = 0
 while (pow2 > 0) {
 if (ans + pow2 > binArray.length || binArray[ans + pow2] == 0) {
 pow2 = pow2 / 2
 continue
 }
 ans += pow2
 pow2 = pow2 / 2
}
 return ans
}

such patterns are very useful in problem-solving. you need to convert your problem into such patterns.

find first number greater than or equal to a given number in the sorted array
[3, 8, 9, 12, 14] , num = 11
[ 1, 1, 1 , 0 , 0 ] make a new array place one where element is smaller than num
given problem  => find number of ones right ? yes

thanks for reading.