best approach for such problems is try to solve for very small numbers then do DP for solve large numbers. as follows single digit = 7,8,9 answer = 3 [i am taking 7 inclussive] double digit= 7*2 = 14. now smallest number can be. 59=1 68, 69 = 2 77 78, 79,=3 86, 87, 88, 89=4 95,96,97,98,99 =5 3 digits. 7*3=21 smallest number= 399=1 489,498,499=3 579, 588,589,597,598,599=6
can you see the pattern? 1 digit = 1,1,1 2n'd digit = 1,2,3,4,5 3rd digit = 1,3,6, 10 now we can easily do DP and get the answer !! :) Happy coding :) On Apr 4, 8:52 pm, bittu <shashank7andr...@gmail.com> wrote: > Hi Geeks, One of The My Friend had This Question in His Technical > Round of Facebook, I m going to share with you.lest see how geek > approach this...Plz don't make this post spam..by discussing whats ur > friend name, wich colge, etc etc..just share your approach, think & > solve the question, even Google search wont give you correct & > efficient approach ,answer for this question..so think your self.. > > O(n^2) Solution is Obvious ..but .it wont work for 10 million as a > limit so not a good solution > > we have to solve it using best approach & algo..as we have > > so here is the question...From Facebook... > > /* > A non-negative integer is called heavy if the average value of its > digits in decimal representation exceeds 7. Assume that 0 has average > value of its digits equal to 0. > > For example the number 8698 is heavy, because the average value of its > digits equal to (8+6+9+8)/4 = 7.75. The number 53141 has the average > value of its digits equal to (5+3+1+4+1)/5 = 2.6, so it is not heavy. > > Write a function > > int heavy_decimal_count(int a,int b); > > that given two non-negative integers A and B returns the number of > heavy integers in the interval [A..B] (both ends included). Assume > that 0 <=A <= B <= 200,000,000 Range Given ..It Really Matters Your > Program should not give time out & memory error > > For example, given A=8,675 and B=8,689 the function should return 5, > because there are 5 heavy integers in range [8,675..8,689]: > > 8675 avg=6.5 > 8676 avg=6.75 > 8677 avg=7 > 8678 avg=7.25 HEAVY > 8679 avg=7.5 HEAVY > 8680 avg=5.5 > 8681 avg=5.75 > 8682 avg=6 > 8683 avg=6.25 > 8684 avg=6.5 > 8685 avg=6.75 > 8686 avg=7 > 8687 avg=7.25 HEAVY > 8688 avg=7.5 HEAVY > 8689 avg=7.75 HEAVY > > you have to keep in mind for given range e.g given B<=2 Billion Its > Man Thing so what happen when > A=1 Billion & B=2 Billion > > */ > > Go Ahead > > Thanks & Regards > Shashank Mani > Cell 9740852296 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
