Problem overview
You get an int[] named nums. BiggestDigitSum returns the number whose digits add up to the most. The digit sum of 472 is 4 + 7 + 2 = 13. If two numbers have the same digit sum, the one that comes first wins. The method returns the number itself, not its digit sum.
For [472, 95, 1000] the digit sums are 13, 14 and 1, so the answer is 95. For [19, 55, 28] all three sums are 10, so 19 wins the tie by coming first. For [0, 7] the sums are 0 and 7, so the answer is 7.
Approach
Again the work is split between a helper and the method that is tested. The helper DigitSum turns one number into its digit sum. BiggestDigitSum then runs a "best so far" loop: start with the first number as the winner, visit the numbers, and replace the winner whenever a number has a strictly bigger digit sum.
The helper takes digits off the right end. n % 10 is the last digit, and n / 10 drops it, because dividing two int values in C# throws away the remainder. Repeating until n reaches 0 visits every digit once.
Step by step
- In
DigitSum, createint total = 0. Forn = 0the loop never runs and 0 is the right answer. - Write
while (n > 0). Each turn removes one digit. - Add
n % 10tototal. For 472 that adds 2. - Set
n = n / 10. Without this linennever changes and the loop never ends. For 472 it leaves 47. - Return
total. - In
BiggestDigitSum, start withint best = nums[0]. - Loop over
numswithforeach. The first pass comparesnums[0]with itself, which changes nothing. - If
DigitSum(num) > DigitSum(best), setbest = num. - Return
best.
The solution in C#
class Solution {
public int DigitSum(int n) {
int total = 0;
while (n > 0) {
total += n % 10;
n = n / 10;
}
return total;
}
public int BiggestDigitSum(int[] nums) {
int best = nums[0];
foreach (int num in nums) {
if (DigitSum(num) > DigitSum(best)) {
best = num;
}
}
return best;
}
}
The details worth knowing:
- Parameters are copies. When
DigitSumchangesn, the caller's number is untouched. - The loop calls
DigitSum(best)again on each pass. That is simple and fast enough here; you could also keep the best digit sum in its own variable. - The numbers go up to 1,000,000,000, which fits in an
int, and digit sums are tiny, so there is no overflow.
Watching the helper work
For 472 the loop takes one digit per turn. This is what each turn does to n and total:
digit 2, n now 47, total 2
digit 7, n now 4, total 9
digit 4, n now 0, total 13
When n reaches 0 the condition n > 0 is false and the loop ends with total equal to 13. The loop runs once per digit, so a 10-digit number takes 10 turns.
Another way to write the helper
You can also turn the number into text and add the characters. Subtracting '0' from a digit character gives its numeric value:
int DigitSum2(int n) {
int total = 0;
foreach (char c in n.ToString()) {
total += c - '0';
}
return total;
}
It returns 13, 14, 1 and 0 for 472, 95, 1000 and 0, the same as the lesson's helper. The remainder-and-divide version is the one to learn first, because it works on the number itself and needs no text.
Keeping the best sum
The solution calls DigitSum(best) again on every pass. A version that stores the best digit sum in a variable of its own calls the helper once per number instead of twice. It returns the same results on the examples, but the lesson's version keeps the code shorter, and the inputs are tiny.
Testing
The helper gives these digit sums for 472, 95, 1000 and 0:
13 14 1 0
On the statement's three examples, BiggestDigitSum returns:
95
19
7
Edge cases and common mistakes
- Using
>=. On a tie it would replace the winner with the later number, so[19, 55, 28]would return 28 instead of 19. Use>. - Returning the digit sum. The answer for
[472, 95, 1000]is 95, not 14. - Forgetting
n = n / 10. The loop then runs forever for any positive number. - Zero. The number 0 has a digit sum of 0 through the empty loop. No special case is needed.
Why the first number starts as the winner
Starting best at nums[0] guarantees that the answer is always a real element of the array, and that earlier numbers win ties, because a later number must be strictly better to replace it. The constraints promise at least one number, so reading nums[0] is safe.
Checking your own version
Test DigitSum alone first: a single digit, a number with a zero inside such as 1000 or 105, and 0 itself. Then test the full method on a tie, since that is where the choice between > and >= shows. Print the returned number and make sure it is an element of the array, not a digit sum.
Also check that the loop in the helper changes only its own copy of the number. The array in BiggestDigitSum keeps its values, so comparing DigitSum(num) and DigitSum(best) many times is safe.
