3945. Digit Frequency Score

EasyHash TableMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

The score of n is defined as the sum of d * freq(d) over all distinct digits d, where freq(d) denotes the number of times the digit d appears in n.

Your task is to return an integer denoting the score of n.

To understand what this means, let's break it down:

For each distinct digit d that appears in n, you multiply the digit value d by how many times it appears, which is freq(d).
You then add up all these d * freq(d) values together.

For example, suppose n = 1233. The distinct digits are 1, 2, and 3:

Digit 1 appears 1 time, contributing 1 * 1 = 1.
Digit 2 appears 1 time, contributing 2 * 1 = 2.
Digit 3 appears 2 times, contributing 3 * 2 = 6.

So the score is 1 + 2 + 6 = 9.

Notice that d * freq(d) for a digit d is exactly the same as adding that digit once for each time it appears. This means the score is simply equal to the sum of all the digits in n. In the example above, the digits of 1233 are 1, 2, 3, and 3, and their sum is 1 + 2 + 3 + 3 = 9, which matches the score.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Using a hash map for constant-time frequency counting enables the solution.

Open in Flowchart

Intuition

The key insight comes from understanding what d * freq(d) actually represents. For a single distinct digit d, multiplying it by the number of times it appears, freq(d), is the same as adding d to itself freq(d) times.

For example, if the digit 3 appears 2 times, then 3 * 2 = 6, which is exactly 3 + 3. In other words, each occurrence of a digit contributes its own value once to the total.

When we sum d * freq(d) over all distinct digits, we are effectively adding every digit of n exactly once for each time it appears. This is precisely the definition of the sum of all digits of n.

So instead of grouping digits, counting their frequencies, and then multiplying, we can directly skip all of that work. The score simplifies to just adding up every digit of n.

Once we realize this, the problem becomes very straightforward: we only need a way to extract each digit of n and accumulate them. We can repeatedly take the last digit using n % 10, add it to our running total, and then remove that digit by doing n // 10. Repeating this until n becomes 0 gives us the sum of all digits, which is the answer.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Simulation

As established in the intuition, the problem reduces to finding the sum of each digit of the number n. We use a simple simulation pattern to extract and accumulate every digit.

The core idea relies on two arithmetic operations:

n % 10 gives us the last digit of n.
n // 10 removes the last digit by performing integer division.

We can use Python's built-in divmod(n, 10) function, which conveniently returns both values at once: the quotient n // 10 and the remainder n % 10.

Here is how the algorithm works step by step:

Initialize a variable ans to 0. This will hold our running sum of digits.
While n is still greater than 0, repeat the following:
- Use divmod(n, 10) to split n into its quotient and remainder. The quotient becomes the new n, and the remainder x is the current last digit.
- Add x to ans.
When n becomes 0, all digits have been processed, so we return ans.

Let's trace through an example with n = 1233:

divmod(1233, 10) → n = 123, x = 3, so ans = 3.
divmod(123, 10) → n = 12, x = 3, so ans = 6.
divmod(12, 10) → n = 1, x = 2, so ans = 8.
divmod(1, 10) → n = 0, x = 1, so ans = 9.
Now n = 0, the loop ends, and we return 9.

This matches the expected score we calculated earlier.

In terms of complexity, the time complexity is O(log n), since the number of digits in n is proportional to log n, and we process each digit exactly once. The space complexity is O(1), as we only use a constant amount of extra space regardless of the size of n.

Example Walkthrough

Let's walk through a small example with n = 405 to see how the simulation extracts and sums each digit.

First, recall the insight: the score is just the sum of all digits of n. For 405, the digits are 4, 0, and 5, so we expect the answer to be 4 + 0 + 5 = 9.

Now let's trace the algorithm step by step. We start with ans = 0 and n = 405.

Iteration 1: n = 405, which is greater than 0, so we proceed.

divmod(405, 10) returns (40, 5). The quotient 40 becomes the new n, and the remainder x = 5 is the last digit.
We add x to our running total: ans = 0 + 5 = 5.
State now: n = 40, ans = 5.

Iteration 2: n = 40, still greater than 0, so we continue.

divmod(40, 10) returns (4, 0). The new n is 4, and x = 0 is the last digit.
We add it: ans = 5 + 0 = 5.
State now: n = 4, ans = 5.

Iteration 3: n = 4, still greater than 0.

divmod(4, 10) returns (0, 4). The new n is 0, and x = 4 is the last digit.
We add it: ans = 5 + 4 = 9.
State now: n = 0, ans = 9.

Loop termination: n is now 0, so the while condition fails and the loop ends. We return ans = 9.

This confirms the result. Notice how the algorithm peeled off one digit at a time from the right (5, then 0, then 4) using n % 10, while n // 10 shrank the number until nothing remained. Even the digit 0 was processed normally, contributing 0 to the sum without any special handling. The final score of 9 matches our expected sum of digits.

Solution Implementation

1class Solution:
2    def digitFrequencyScore(self, n: int) -> int:
3        # Accumulator for the sum of all digits
4        total = 0
5
6        # Process each digit from the least significant to the most significant
7        while n:
8            # Split n into its remaining higher digits (quotient)
9            # and the current last digit (remainder)
10            n, digit = divmod(n, 10)
11
12            # Add the extracted digit to the running total
13            total += digit
14
15        # Return the final digit sum
16        return total
17

1class Solution {
2    /**
3     * Computes the sum of all decimal digits of the given number.
4     * (Note: the method name is preserved as required, though the
5     *  logic performs a digit-sum rather than a frequency score.)
6     *
7     * @param n the non-negative integer to process
8     * @return the sum of the digits of n
9     */
10    public int digitFrequencyScore(int n) {
11        // Accumulator for the running total of digits.
12        int digitSum = 0;
13
14        // Process each digit from least significant to most significant.
15        // The loop stops once all digits have been consumed (n becomes 0).
16        for (; n > 0; n /= 10) {
17            // Extract the current last digit and add it to the total.
18            digitSum += n % 10;
19        }
20
21        // Return the accumulated sum of all digits.
22        return digitSum;
23    }
24}
25

1class Solution {
2public:
3    // Computes the sum of all digits of a non-negative integer n.
4    // Despite the method name, this function calculates the digit sum.
5    int digitFrequencyScore(int n) {
6        int sum = 0;  // Accumulator for the sum of digits
7
8        // Process each digit from least significant to most significant
9        for (; n > 0; n /= 10) {
10            sum += n % 10;  // Extract the last digit and add it to the sum
11        }
12
13        return sum;  // Return the total digit sum
14    }
15};
16

1/**
2 * Calculates the sum of all digits in the given number.
3 *
4 * @param n - The non-negative integer whose digits will be summed.
5 * @returns The sum of all digits of n.
6 */
7function digitFrequencyScore(n: number): number {
8    // Accumulator for the total digit sum.
9    let sum = 0;
10
11    // Process each digit from least significant to most significant.
12    // Loop continues while n is truthy (i.e., n !== 0).
13    for (; n > 0; n = Math.floor(n / 10)) {
14        // Extract the last digit using modulo and add it to the sum.
15        sum += n % 10;
16    }
17
18    return sum;
19}
20

Time and Space Complexity

Time Complexity: O(log n). The while loop runs once for each digit of n. Since a number n has approximately log₁₀ n digits, each iteration of the loop reduces n by a factor of 10 (via divmod(n, 10)). Therefore, the total number of iterations is proportional to the number of digits, which is O(log n).
Space Complexity: O(1). Only a constant number of variables (ans, n, and x) are used, regardless of the size of the input n. No additional data structures that scale with the input are allocated.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Overcomplicating the Solution with Frequency Counting

A common mistake is taking the problem statement too literally and building an explicit frequency map before computing the score. While this approach is correct, it adds unnecessary complexity and overlooks the key mathematical insight that score = sum of all digits.

Problematic approach:

class Solution:
    def digitFrequencyScore(self, n: int) -> int:
        from collections import Counter
        freq = Counter()

        # Count occurrences of each digit
        while n:
            n, digit = divmod(n, 10)
            freq[digit] += 1

        # Multiply each distinct digit by its frequency
        total = 0
        for d, f in freq.items():
            total += d * f
        return total

This works, but it uses O(1) extra space for the counter (bounded by 10 digits) and two passes' worth of logic. The reduction d * freq(d) summed over distinct digits is mathematically identical to summing every digit once per appearance, so the frequency map is redundant.

Solution: Recognize that score = sum of digits and use the single-pass digit extraction shown in the main solution.

Pitfall 2: Handling `n = 0` Incorrectly

If n is 0, the while n: loop never executes because 0 is falsy in Python. This is actually the correct behavior — the score of 0 is 0 — but developers sometimes assume the loop must run at least once and add special-case handling or a do-while-style workaround that introduces bugs.

Problematic approach:

class Solution:
    def digitFrequencyScore(self, n: int) -> int:
        total = 0
        # Forcing at least one iteration breaks for multi-digit numbers
        # or double-counts when not careful
        n, digit = divmod(n, 10)
        total += digit
        while n:
            n, digit = divmod(n, 10)
            total += digit
        return total

For n = 0, this still returns 0 by luck, but the unrolled first iteration is fragile and harder to reason about.

Solution: Trust that while n: naturally handles n = 0 by returning the initialized total of 0. No special casing is needed.

Pitfall 3: Assuming Negative Inputs

If the problem ever allows negative n, the while n: loop misbehaves because divmod with negative numbers in Python produces unexpected signs (e.g., divmod(-1233, 10) returns (-124, 7)), and the loop condition while n: may not terminate cleanly toward 0.

Solution: If negatives are possible, normalize the input first with n = abs(n) before entering the loop. For this problem, n is a non-negative integer, so the base solution is safe, but guarding with abs(n) makes the code more robust:

class Solution:
    def digitFrequencyScore(self, n: int) -> int:
        total = 0
        n = abs(n)  # Defensive guard against negative input
        while n:
            n, digit = divmod(n, 10)
            total += digit
        return total

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: