OK, here's my rather rambling theory on how to approach it: First break the range down into a series of smaller ranges into form:
xxyzz where: xx is 0 to n digits which are fixed throughout the range. y is 0 or 1 digit in the range 0..n or m..9 (with a special case *) zz is 0 to n digits in the range 0..9 (The special case cited above is that y can be in the range m..n if there are no z digits, that is, the entire range of the problem is less than 10) So, if we were given the range [8675...8788], our subranges would break down as such: [8675-8679] (xxx=867, y = 5..9) [8680-8699] (xx=86, y=8..9, z=0..9) [8700-8779] (xx=87, y=0..7, z=0..9) [8780-8788] (xxx=878, y=0..8) We'll use the [8700-8779] range to contiune. Since our goal is an average greater than 7, we need a sum of all digits greater than 28. So, we first calculate the sum of the x digits. (here, 15), Then for each digit in the y range we calculate 10 - (29- 15 - y). If the number is greater than zero, it's the number of heavy numbers for than value of y. for example: y = 0, 10 - (29-15-0) = -4, no heavy numbers y = 1, 10 - (29-15-1) = -3, no heavy numbers y = 2, 10 - (29-15-2) = -2, no heavy numbers y = 3, 10 - (29-15-3) = -1, no heavy numbers y = 4, 10 - (29-15-4) = 0, no heavy numbers y = 5, 10 - (29-15-5) = 1, 1 heavy number (spec, 8759) y = 6, 10 - (29-15-6) = 2, 2 heavy numbers (spec, 8768, & 8769) y = 7, 10 - (29-15-7) = 3, 3 heavy numbers (spec, 8777, 8778, & 8779) Hence we have determined that there are 3 heavy numbers in the range [8700-8779]. Our next improvement is to recognize the pattern in the above, and realize that we don't need to go looping through the full range, we just need to determine the pivot point : The value of y which there exists some values of z which yield a heavy number. So, with N = number of digits T = Minimum sum of digits needed for a "heavy" number (i.e., N*7 +1) X = Sum of digits in xx portion of number, then Pivot = (T -X) - 10 So, using our example, N=4, T=29, X=15 and therefore the pivot = 4 then low = max(0, m-Pivot) high = n-Pivot (m & n as defined way above, here, m = 0, n = 7, so low = 0, high = 7-4 = 3) finally, # of Heavy num in range = Sumation low -> high (here, 0+1+2+3 = 6) That gives us a simple mechancal process to divide the range into subrange, and a simple formula for calculating the value for each subrange. However, this process falls apart if the zz section is more than 1 digit. However, I believe it can be salvaged with some small tweaks, but I will leave that to the next guy...... On Apr 4, 11: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.
