Digit Frequency Score | LeetCode 3945 | Weekly Contest 504 | Java | Developer Coder
Digit Frequency Score - Video Solution
Watch 10 video solutions for Digit Frequency Score, a easy level problem involving Hash Table, Math. This walkthrough by Developer Coder has 178 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
nis1 + 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
nis 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.
Complexity Analysis
| Approach | Time | Space | When 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 Count | O(n) | O(k) | General solution when characters or symbols are not limited to a small range |
| Fixed Array Digit Counting | O(n) | O(1) | Best option when working with digits 0-9 because the range is constant |