Start learning free

LESSON 243 OF 667 · HELPER FUNCTIONS

Biggest Digit Sum in C++: Compare Numbers with a Helper

Practice Read the full explanation

You get a vector of integers nums. Return 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, return the one that comes first.

The work is split between two functions. The first one is a helper. It gets one number and returns the sum of its digits. The second one is the function that is graded. It uses the helper to compare the numbers.

 

Example 1:

Input: nums = [472, 95, 1000]
Output: 95
Explanation: The digit sums are 13, 14 and 1.
95 has the biggest one: 9 + 5 = 14.

Example 2:

Input: nums = [19, 55, 28]
Output: 19
Explanation: All three digit sums are 10.
19 comes first, so it wins the tie.

Example 3:

Input: nums = [0, 7]
Output: 7
Explanation: The digit sum of 0 is 0.
The digit sum of 7 is 7.

 

Constraints:

  • nums has at least one number.
  • Every number is between 0 and 109.
  • Return the number itself, not its digit sum.
STEP 1 OF 9
    Ctrl + Enter to check

    C++ · HELPER FUNCTIONS

    Biggest Digit Sum in C++, explained

    Problem overview

    The function biggestDigitSum gets a vector of integers nums and 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 function returns the number itself, not its digit sum. Every number is between 0 and a billion, and there is at least one.

    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 the first one, 19, wins. For {0, 7} the sums are 0 and 7, so the answer is 7.

    The work is split in two functions. The helper digitSum returns the sum of the digits of one number. biggestDigitSum uses it to compare the numbers.

    Approach

    The helper: peeling off digits

    For a whole number n, n % 10 is its last digit (472 % 10 is 2) and n / 10 drops the last digit, because dividing two int values throws the remainder away (472 / 10 is 47). So a loop that adds n % 10 to a total and then replaces n with n / 10 visits every digit from right to left. It stops when n reaches 0. For n = 0 the loop never runs and the sum is 0, which is the right answer.

    The main function: best so far

    Keep the winner so far in best, starting with the first number. For each number, compare its digit sum with the digit sum of best, and replace best only when the new sum is strictly greater. A strict comparison is what makes ties go to the number that came first.

    Peeling off 472

    Here is the helper's loop on 472:

    • with n = 472 the last digit is 2, and n becomes 47;
    • with n = 47 the last digit is 7, and n becomes 4;
    • with n = 4 the last digit is 4, and n becomes 0, so the loop stops.

    The total is 2 + 7 + 4 = 13. The digits come out from right to left, which doesn't matter for a sum.

    Step by step

    1. In digitSum, create total as an int starting at 0.
    2. Loop while n > 0. Each turn removes one digit.
    3. Add the last digit n % 10 to total.
    4. Drop the last digit by storing n / 10 back in n. Without this line, the loop never ends.
    5. Return total.
    6. In biggestDigitSum, set best to nums[0].
    7. Loop over nums with an int named num. The first turn compares the first number with itself, which changes nothing.
    8. If digitSum(num) > digitSum(best), set best to num.
    9. Return best after the loop.

    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;
    }

    int biggestDigitSum(vector<int> &nums) {
        int best = nums[0];
        for (int num : nums) {
            if (digitSum(num) > digitSum(best)) {
                best = num;
            }
        }
        return best;
    }
};

    Notes on the C++:

    • digitSum takes n by value, so the loop can change n without touching the caller's number.
    • Numbers up to a billion fit in an int, and a digit sum is at most 81, so nothing overflows.
    • The helper is called twice per comparison, once for num and once for best. That is simple, and each call costs only about ten turns of its loop.

    Following the tie

    For {19, 55, 28}, best starts as 19, whose digit sum is 10. Then 19 is compared with itself, which is not greater. 55 has a digit sum of 10, which is not greater than 10, so best stays 19. The same happens for 28. The answer is 19, the first number with the biggest sum.

    The code calls digitSum(best) again on each turn instead of storing the winner's sum in a second variable. Storing it would save some work and is a fine alternative, but the version shown is shorter and fast enough for these inputs.

    Complexity

    A number with d digits takes d turns of the helper loop, and a number up to a billion has at most ten. The main function makes two helper calls per number, so the work is proportional to the length of nums, times a small constant. Space is O(1), since only a few integers are kept.

    Edge cases and common mistakes

    • Ties. With >= instead of >, {19, 55, 28} would return 28, since every later tie replaces the winner.
    • Zero. digitSum(0) is 0 because the loop doesn't run.
    • Forgetting n = n / 10. The loop keeps seeing the same n and never ends.
    • Returning the sum. For {472, 95, 1000} the answer is 95, not 14.
    • Numbers with zeros inside. 1000 has the digits 1, 0, 0 and 0, and the zeros add nothing. The sum is 1.

    Testing

    • {472, 95, 1000} gives 95.
    • {19, 55, 28} gives 19.
    • {0, 7} gives 7.
    • {999999999, 1000000000} gives 999999999: the digit sums are 81 and 1. The biggest allowed number does not have the biggest digit sum, which is a good reminder that the helper, and not the size of the number, decides.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free