Subject: RE: Re: Facebook Interview Question....Heavy Number Newsgroups: gmane.comp.programming.algogeeks Date: Tuesday 5th April 2011 16:27:36 UTC (over 7 years ago) Hey James Would that work equally well for 59 up to 10009999? Sent from my Windows Phone From: James Curran Sent: Tuesday, April 05, 2011 7:50 AM To: Algorithm Geeks Subject: [algogeeks] Re: Facebook Interview Question....Heavy Number 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 |
|||