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 <[email protected]> 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 [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.
>
>
--
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.
