Well, for the algorithm posted (which, in case you didn't figure out, I was
makeing up as I went), the subranges have to have the same number of
digits. That means our subranges would be:
[59]
[60..99]
[100..999]
[1000..9999]
[10000..99999]
[100000..999999]
[1000000..9999999]
[10000000..10009999]
And this is where we hit into the "multi-digit Z" problem I referred to in
my last line.
But, I just realized, most ranges, once put into the canonic sub-range form,
yield many common subranges (e.g, the 2nd, 3rd, 4th, 5th, 6th, & 7th given
above). This gives us the simple solution for most of them -- Do it once
manually, and there after use a lookup table.
0-9: Easy 8 & 9
00-99: 69, 78, 79, 87, 88, 89, 96, 97, 98, 99
etc. although the line starting getting long after that: 000-999 starts @
499
But the 00-99 gives us a patterns we might be able to exploit:
69
78 79
87 88 89
96 97 98 99
for 000-999 :
499
589 598 599
679 688 689 697 698 699
769 778 779 787 788 789 796 797 798 799
still a pattern, but less obvious....
Truth,
James
On Tue, Apr 5, 2011 at 12:27 PM, Hamilton Verissimo de Oliveira <
[email protected]> wrote:
> 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......
>
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
