Link to problem statement on HackerRank
What happened in my mind : After I read the problem statement, first I was shocked by the length of input. But then I payed a little attention and tried to calculate running time of the worst case.
if n is of length 100,000 and all of it's digits are 9, then we have 100,000 9s if we repeat them k=100,000 times we would have 100,000 x 100,000 9's. For the first round we calculate sum of input and multiply it by k.
Now the largest number we can get after first round is 90,000,000,000 which has 11 digits,
if we calculate sum of digits of this number it would be at most 2 digits, (eleven 9s).
So it became an easy problem after these calculations.
The only key is to sum digits of input and multiply it by k, instead of creating a number with k copies of input.
For more details look at my code on github.
What happened in my mind : After I read the problem statement, first I was shocked by the length of input. But then I payed a little attention and tried to calculate running time of the worst case.
if n is of length 100,000 and all of it's digits are 9, then we have 100,000 9s if we repeat them k=100,000 times we would have 100,000 x 100,000 9's. For the first round we calculate sum of input and multiply it by k.
Now the largest number we can get after first round is 90,000,000,000 which has 11 digits,
if we calculate sum of digits of this number it would be at most 2 digits, (eleven 9s).
So it became an easy problem after these calculations.
The only key is to sum digits of input and multiply it by k, instead of creating a number with k copies of input.
For more details look at my code on github.
No comments:
Post a Comment