I am not sure if I can explain the general approach as efficiently as by explaining with an example: for the example you have give , say to find for A= 1,000,000,000 - 2,000,000,000 first two billion is not heavy.
So finding from 1,000,000,000 - 1,999,999,999 It is:( 1 + sigma (x) ) > 70 , where sigma( x ) is the sum of the rest of the nine integers. so, sigma(x) > 69. so its now a problem of finding the sum of 9 digits to exceed the sum 69. If someone could work this permutation problem please put it up, I am trying to come up with an accurate formula for this. Generalizing, split the range into units that can be brought into this workable form and apply the formula. On Mon, Apr 4, 2011 at 8:52 AM, 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. > > -- Best, T Anand Karthik, Contact number: +91-9571552652 -- 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.
