Re: [algogeeks] Re: Facebook Interview Question....Heavy Number
http://codegolf.stackexchange.com/questions/2952/count-number-of-hefty-decimals-between-2-numbers -- 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.
[algogeeks] Re: Facebook Interview Question....Heavy Number
best approach for such problems is try to solve for very small numbers then do DP for solve large numbers. as follows single digit = 7,8,9 answer = 3 [i am taking 7 inclussive] double digit= 7*2 = 14. now smallest number can be. 59=1 68, 69 = 2 77 78, 79,=3 86, 87, 88, 89=4 95,96,97,98,99 =5 3 digits. 7*3=21 smallest number= 399=1 489,498,499=3 579, 588,589,597,598,599=6 can you see the pattern? 1 digit = 1,1,1 2n'd digit = 1,2,3,4,5 3rd digit = 1,3,6, 10 now we can easily do DP and get the answer !! :) Happy coding :) On Apr 4, 8:52 pm, 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.
Re: [algogeeks] Re: Facebook Interview Question....Heavy Number
Ok. Here's a possible O(n) solution.
Assuming last digit of a is 0.
for(n=a;n=b;n+=10)
{
Calculate the sum of digits, leaving the last digit.
Find the minimum value of last digit for it to be a heavy number.
Increment count by 10-that number.
}
So here, complexity will be: O(n/10*(d-1))
where, d is the number of digits in the number, which is always less than
10.
So it'll be O(n).
On Tue, Apr 5, 2011 at 3:10 PM, bittu shashank7andr...@gmail.com wrote:
@all , Nikhi Jindal ,.as i already told that O(n^2) Solution is
Obvious ..but .it wont work for 1Biillion as a time
limit exceeds , memory Error occur, so its not a good solution ..I
think There is DP Solution Exist For Thats We Need to Figure it Out to
resolve this problem
@anand what r u trying to do bro...elaborate something more
let me know if still have confusion ??
Thanks Regards
Shashank Mani
--
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.
--
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.
[algogeeks] Re: Facebook Interview Question....Heavy Number
@all , Nikhi Jindal ,.as i already told that O(n^2) Solution is Obvious ..but .it wont work for 1Biillion as a time limit exceeds , memory Error occur, so its not a good solution ..I think There is DP Solution Exist For Thats We Need to Figure it Out to resolve this problem @anand what r u trying to do bro...elaborate something more let me know if still have confusion ?? Thanks Regards Shashank Mani -- 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.
[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...@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.
RE: [algogeeks] Re: Facebook Interview Question....Heavy Number
Hey James Would that work equally well for 59 up to 1000? Sent from my Windows Phone From: James Curran Sent: Tuesday, April 05, 2011 7:50 AM To: Algorithm Geeks Subject: [algogeeks] Re: Facebook Interview QuestionHeavy 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...@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
Re: [algogeeks] Re: Facebook Interview Question....Heavy Number
Hey , i m a new follower to this group.. i was actually looking for a nice group that would contain a nice challenge to sharpen the brain. and i finally ended with this group... i m happy to follo this group along with geeks like you. -- 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.
Re: [algogeeks] Re: Facebook Interview Question....Heavy Number
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..] [1..9] [10..99] [100..999] [1000..1000] 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 hamm...@gmail.com wrote: Hey James Would that work equally well for 59 up to 1000? Sent from my Windows Phone From: James Curran Sent: Tuesday, April 05, 2011 7:50 AM To: Algorithm Geeks Subject: [algogeeks] Re: Facebook Interview QuestionHeavy 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 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.
