I came across this question in one of the interviews. I struggled to clear all the test cases and was hoping to know if someone has a better solution for this question:

Given a number N in form of a binary string (1<=N<=2^{10^5}), count total set bits in all numbers from 1 to N.

I have tried solving the problem using this algorithm but was able to clear only a few test cases.

Really appreciate the help!

`int`

`getSetBitsFromOneToN(`

`int`

`N){`

` `

`int`

`two = 2,ans = 0;`

` `

`int`

`n = N;`

` `

`while`

`(n){`

` `

`ans += (N/two)*(two>>1);`

` `

`if`

`((N&(two-1)) > (two>>1)-1) ans += (N&(two-1)) - (two>>1)+1;`

` `

`two <<= 1;`

` `

`n >>= 1;`

` `

`}`

` `

`return`

`ans;`

`}`

**USE THIS it will work in O(logn)**

N is a string not an integer, this solution wonâ€™t work.