Let **n** be the number given and **d** be number of digits in n.

Let **ones[d]** be equal to number of 1 in all numbers upto biggest number of d digits.

Let **msd** be the digit at highest place value/

Let **rem** be number without msd. (eg n = 1234, rem = 234, msd = 1)

**Recursion formula:**

ans(n) = ones[d-1] + (ones[d-1]*(msd-1)) + [msd == 1 :: (rem+1) ? pow(10,d-1)] + ans(rem)

Using this recursive solution we can find the answer.

**Calculating ones[ ]**

ones[0] = 0;

ones[1] = 1;

ones[i] = 10*ones[i-1] + pow(10, i-1);