10427 - Naughty Sleepy Boys
Solution Description : start 1 end 9: 1 digit number= 9 digit=1*9=9 start 10 end 99: 2 digit number=90 digit=2*90=180 total digit=9+180=189 start 100 end 999: 3 digit number=900 digit=3*900=2700 total digit=189+2700=2889 start 1000 end 9999: 4 digit number=9000 digit=4*9000=36000 total digit=2889+36000=38889 and so on............ You need to store start value and total digit for 1 digit number to 8 digit number so you can got start[0]=0 totaldigit[0]=0 block 0 start[1]=1 totaldigit[1]=9 block 1 start[2]=10 totaldigit[2]=189 block 2 start[3]=100 totaldigit[3]=2889 block 3 .............................. start[8]=10000000 totaldigit[8]=788888889 block 8 Now input n you can find easily n in which block. if n=3 then it is in block 1 i.e. 1 digit number block, because totaldigit[0]<n<totaldigit[1] if n=10 then it is in block 2 i.e. 2 digit number block, because totaldigit[1]<n<totaldigit[2] if n=100 then it is in block 2 i.e. 2 digit number block, because totaldigit[1]<n<totaldigit[2] so, you can find the start number for this block if n=10 then it is in block 2 and start number = start[block]=start[2]=10 now set m = n - totaldigit[block] // if n=10 then m = 10 - totaldigit[2] = 10 - 9 = 1 now find the number (num) which contain n'th digit set x =(long) m / block // if n=10 then x = 1/2 = 0, if n=11 then x = 2/2=1, if n=12 then x=3/2=1 if x*block == m then x = x-1 // for n=10 -> x=0, n=11 -> x=0, n=12 -> x=1 num = start[block]+x // for n=10 -> num=10+0=10, n=11 -> num=10+0, n=11 -> num=10+1=11 digitNum=m%block if digitNum==0 then digitNum=block // for n=10 -> digitNum=1, n=11 -> digitNum=2, n=12 -> digitNum=1 finally you got the ans num digitNum ans n=10 10 1 1 n=11 10 2 0 n=12 11 1 1 |
||||||||||
10409 - Die Game