Youri's answer is correct in terms of general code review.
What I want to address here is that you can rework your algorithm to skip some unnecessary steps. You're taking the brute force approach, but there's a more clever way to think about this.
I'm going to take the long way to explain this, because I think it's important for you to see how I came to this solution; rather than just seeing the end result. The purpose here is to learn how to analyze how numbers behave.
For the entirety of this answer, I'm counting digits beginning from the right. The "first" digit is the rightmost digit (100), the "second" digit is the second-rightmost digit (101), the "third" digit is the third-rightmost digit (102), and so on.
First of all, try to think of each digit like a container that can be filled up to 9. Since you're only interested in the sum of the digits, it doesn't matter (in regards to the sum) which containers you increase.
However, you are trying increment the original number. Counting up means that you increase the rightmost number first. Therefore, when looking for your result, you increase the first digit, up to 9. Let's assume you haven't found it by now. You would then roll over to the second digit.
But when you roll over to the second digit, the first digit goes back to 0. You gain
+1 from the second digit, but you lose
-9 from the first digit. It makes no sense to even try and check this number, because if the previous number was not high enough, this one definitely won't be.
Even if you only brought the first digit down to an 8, you end up gaining
+1 from the second digit, but you still lose
-1 from the first digit, which is a zero sum game.
The conclusion here is that decreasing the digits when rolling over negatively impacts the total sum of the digits, and therefore doesn't make sense. When a digit reaches 9, you can keep it at 9, and just start increasing the next digit.
Let's use 765 as an example. The target sum is (7+6+5)*2 = 36. Let's start checking:
766 = 19
767 = 20
768 = 21
769 = 22 <---------- First number reaches 9
770 = 14
771 = 15
772 = 16
773 = 17
774 = 18
775 = 19
776 = 20
777 = 21
778 = 22
779 = 23 <---------- First sum to be higher than the 22 I point out earlier
Notice how numbers 770 to 778 were irrelevant, because their sum was lower than what we had already found. There was no reason to check any of them.
You only need to check numbers with a higher sum than you already found.
Here's a list of numbers, starting from 766, which are actually a higher total sum than you've ever seen before
766 = 19
767 = 20
768 = 21
769 = 22
779 = 23
789 = 24
799 = 25
899 = 26
999 = 27
1999 = 28
2999 = 29
3999 = 30
4999 = 31
5999 = 32
6999 = 33
7999 = 34
8999 = 35
9999 = 36 <------ FOUND IT
There are interesting things to notice about the sequence:
- The first digit increased up to 9 and then stayed there forever.
- The second digit increased up to 9 and then stayed there forever.
- The third digit increased up to 9 and then stayed there forever.
You can use this to your advantage, because now you know how you can find the next number in the sequence:
- Find the rightmost digit that is not already 9 and increment it.
- If all digits are 9, prepend a 1.
Or, in code (I am a C# dev, the syntax should mostly match):
private int GetNextRecordBreakingNumber(int number)
// Split the number into an array of its digits
int digits = number.ToString().Select(c => c - '0').ToArray();
// Count indices from right to left
for(int i = digits.Length - 1; i >= 0; i--)
if(digits[i] != 9)
// Increment the non-9 digit
digits[i] = digits[i] + 1;
//Put the number back together and return it
int result = 0;
for(int j = 0; j < digits.Length; j++)
result = result * 10 + digits[j];
// If we get here, all digits were 9, so just add 10^X (where X = amount of digits in old number)
return number + (int)Math.Pow(10, digits.Length);
I opted for the string-based approach to separate a number into its digits, as it is much easier to read than the mathematical approach, and the performance should not form any problem, as I will discuss below the break.
This will sequentially generate the list I showed you before:
int current = 765;
for(int i = 0; i < 18; i++)
current = GetNextRecordBreakingNumber(current);
link to fiddle.
If you use this method to find the next number, instead of doing
k++;, this will cost you significantly less iterations.
10 => 11 and
99 => 9999 examples prove that your code will iterate at least once, and up to
n orders of magnitude (where
n is the number of digits of your starting value) higher than where you started. That is massive when dealing with non-trivial numbers.
Using my suggested method, you cut down the maximum iterations to
n*9. (Edit: I think this is even lower, closer to
n*5 on average, but I'm fuzzy on the math here)
Case in point:
99 => 9999. Your logic would perform 9900 iterations. My logic would perform 18.