A DP problem

Giorgi · Post by **Giorgi** » Sat Oct 06, 2007 11:26 am

I want to solve problem on the contest and I need your help.

I have number n and I want to find out how many digit 1 - s are in the numbers from 1 to n. how to solve it? n < 10^20.

for exapmle for n = 15 answer is 8

1
10
11
12
13
14
15

there are 8 one from 1 to 15. help please
thanks

sclo · Post by **sclo** » Sat Oct 06, 2007 3:23 pm

write out the binary of 0 to n on each row, and look for a pattern on each column.

The rightmost column is like this: 01010101...
The second rightmost column: 00110011...
next column: 00001111...

Giorgi · Post by **Giorgi** » Tue Oct 30, 2007 3:00 pm

I can't understand

can you or others explain it to me more clearly?