Skip to main content
Talentd

Digit Frequency Score - Solution & Explanation

EasyHash TableMath5 min read
Practice this problem

Problem Statement

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.

Return an integer denoting the score of n.

 

Example 1:

Input: n = 122

Output: 5

Explanation:

  • The digit 1 appears 1 time, contributing 1 * 1 = 1.
  • The digit 2 appears 2 times, contributing 2 * 2 = 4.
  • Thus, the score of n is 1 + 4 = 5.

Example 2:

Input: n = 101

Output: 2

Explanation:

  • The digit 0 appears 1 time, contributing 0 * 1 = 0.
  • The digit 1 appears 2 times, contributing 1 * 2 = 2.
  • Thus, the score of n is 2.

 

Constraints:

  • 1 <= n <= 109

Approach Overview

Problem Overview: You receive a number or digit string and must compute a score derived from how often each digit appears. The task reduces to counting occurrences of digits (0–9) and applying the rule defined in the problem to produce the final score.

Approach 1: Recount Digits for Every Check (Brute Force) (Time: O(n^2), Space: O(1))

One straightforward approach repeatedly scans the string to determine how often each digit appears. For every digit you encounter, iterate through the entire string again and count matches. After collecting these counts, apply the scoring rule (for example comparing highest and lowest frequencies or applying weights). This works but wastes time because the same digits are counted many times. It’s mainly useful to demonstrate the baseline logic before optimizing.

Approach 2: Hash Map Frequency Counting (Time: O(n), Space: O(k))

A better solution stores digit counts while scanning the string once. Use a hash table where the key is the digit and the value is its frequency. Each character is processed with a constant-time hash lookup and increment. Once the pass finishes, iterate through the stored counts and compute the score according to the problem rule. This removes repeated scans and reduces the runtime to linear. This approach uses concepts from hash maps and basic frequency counting.

Approach 3: Fixed-Size Digit Array (Optimal) (Time: O(n), Space: O(1))

Digits are limited to 0–9, so a hash map is unnecessary. Instead, allocate an integer array of size 10 and treat each index as the frequency counter for a digit. Iterate through the string once, convert each character to its numeric value, and increment freq[digit]. After counting, iterate through the 10 slots and compute the score using the stored frequencies. This keeps the algorithm linear while using constant extra memory. The technique relies on simple array indexing and is usually the cleanest implementation.

Recommended for interviews: The fixed-size array counting approach is what interviewers typically expect. The brute-force method shows you understand the underlying task, but the optimal array-based frequency count demonstrates awareness of constraints and efficient use of constant-size structures.

Solution

The problem is equivalent to finding the sum of each digit of a number. We can obtain each digit by repeatedly taking the modulus and dividing by 10, and accumulate the result.

The time complexity is O(log n), where log n is the number of digits in n. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Counting (Brute Force)O(n^2)O(1)Useful for understanding the problem logic or when input size is extremely small
Hash Map Frequency CountO(n)O(k)General solution when characters or symbols are not limited to a small range
Fixed Array Digit CountingO(n)O(1)Best option when working with digits 0-9 because the range is constant

Video Solution

Digit Frequency Score | LeetCode 3945 | Weekly Contest 504 | Java | Developer Coder • Developer Coder • 178 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Digit Frequency Score easy or hard?
Digit Frequency Score is generally classified as an easy problem. The core requirement is recognizing that counting digit occurrences simplifies the task. Once frequencies are stored, computing the final score becomes a straightforward constant-time operation.
Digit Frequency Score Python/Java solution
Most implementations iterate through the string and increment a counter for each digit. In Python, a list of size 10 or collections.Counter can be used. In Java, an int[10] array is common. Both versions run in O(n) time and constant extra space when using the fixed array.
How to solve Digit Frequency Score in O(n)?
Scan the digit string once and maintain a frequency array of length 10. For each character, convert it to its numeric value and increment the corresponding index. After counting all digits, apply the scoring rule using the stored frequencies. This single-pass counting strategy guarantees O(n) runtime.
What is the best approach for Digit Frequency Score?
The most efficient solution counts digit occurrences using a fixed array of size 10. Each digit from the input is processed once and its counter is incremented. After building the frequency table, the score is computed directly from those counts. This runs in O(n) time with O(1) extra space.
Is Digit Frequency Score asked at Google/Amazon/Meta?
Frequency counting problems appear frequently in technical interviews at large companies including Google, Amazon, and Meta. Variants often involve counting characters, digits, or elements and deriving a value from those counts. The core technique—efficient counting with arrays or hash maps—is widely tested.
What data structure is used in Digit Frequency Score?
The problem is typically solved with either a hash map or a fixed-size integer array. Because digits range from 0 to 9, a simple array of size 10 is usually preferred. This provides constant-time updates and avoids the overhead of hashing.
What is the time complexity of Digit Frequency Score?
The optimal implementation runs in O(n) time where n is the number of digits in the input. Each digit is processed exactly once during frequency counting. A small constant pass over the 10-digit frequency array may follow, which does not affect the linear complexity.

Ready to solve this problem?

Practice Digit Frequency Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters