Tuesday, September 23, 2008

Problem Of The week 23

Let f(n) be the number of 1s in all numbers from 1to n. then f(1)=1, f(8 )=1 and f(10)=2 and f(11)=4. Find f(10^100)?

A) 10^99+1 B) 10^100+1 C) 10^101+1 D) 10^102+1 E) None of these.

4 comments:

  1. f(1)=1
    f(10)=2
    Now, since the number in question is v. large, we'll try to generalize.
    Counting the no. of 1s upto 100
    1/21/31/41/51/61/71/81/91=9 and 10/11/12/13/14/15/16/17/18/19=10+1 and 1 in 100
    So, f(100)=21
    Now, for f(1000), for each slot of hundred we get 20 1s(excluding the hundred's digit in 100-199). And 100 1s in hundreds place
    So, total 1s=20*10+100+1(for 1000)=301
    Now, f(10^1)=2=1*10^0+1
    f(10^2)=2*10^1+1=21
    f(10^3)=3*10^2+1
    So, the generalization is f(10^n)=n*10^(n-1)+1
    so, f(10^100)=100*10^99+1=10^101+1
    Answer is C

    ReplyDelete
  2. implex, is this correct?

    ReplyDelete