Picon

RE: Re: Facebook Interview Question....Heavy Number

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 <shashank7andr...@...> 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@...
To unsubscribe from this group, send email to
algogeeks+unsubscribe@...
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

--

-- 
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@...
To unsubscribe from this group, send email to algogeeks+unsubscribe <at> googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.


Gmane