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.
