Check if Number Has Equal Digit Count and Digit Value
EasyPrompt
You are given a 0-indexed string num of length n consisting of digits.
Return true if for every index i in the range 0 <= i < n, the digit i occurs num[i] times in num, otherwise return false.
Example 1:
Input: num = "1210"
Output: true
Explanation:
num[0] = '1'. The digit 0 occurs once in num.
num[1] = '2'. The digit 1 occurs twice in num.
num[2] = '1'. The digit 2 occurs once in num.
num[3] = '0'. The digit 3 occurs zero times in num.
The condition holds true for every index in "1210", so return true.Example 2:
Input: num = "030"
Output: false
Explanation:
num[0] = '0'. The digit 0 should occur zero times, but actually occurs twice in num.
num[1] = '3'. The digit 1 should occur three times, but actually occurs zero times in num.
num[2] = '0'. The digit 2 occurs zero times in num.
The indices 0 and 1 both violate the condition, so return false.
Constraints:
n == num.length1 <= n <= 10numconsists of digits.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through each index i of the string and, for each i, it performs another iteration through the entire string to count the occurrences of the digit i. It then compares this count with the expected count given by num[i].
Algorithm
- Iterate through the string
numwith an indexifrom0ton-1, wherenis the length of the string. - For each index
i, determine the expected count of the digiti. This is the integer value of the characternum[i]. Let's call itexpectedCount. - Initialize a counter
actualCountto zero. - Start a nested loop to iterate through the string
numagain with an indexjfrom0ton-1. - Inside the nested loop, check if the digit at
num[j]is equal to the digiti. - If
(num.charAt(j) - '0') == i, incrementactualCount. - After the nested loop finishes, compare
expectedCountwithactualCount. - If
expectedCountis not equal toactualCount, the condition is violated, so returnfalseimmediately. - If the outer loop completes without finding any mismatch, it means the condition holds for all indices. Return
true.
Walkthrough
The brute-force method involves a straightforward, nested-loop implementation. The outer loop iterates through each possible digit i from 0 to n-1, where n is the length of the string. For each digit i, the inner loop traverses the entire string num to count how many times i actually appears. This actualCount is then compared with the expectedCount, which is derived from the character num[i].
class Solution { public boolean digitCount(String num) { int n = num.length(); for (int i = 0; i < n; i++) { // The digit i should appear num[i] times. int expectedCount = num.charAt(i) - '0'; int actualCount = 0; // Count the actual occurrences of digit i in the string. for (int j = 0; j < n; j++) { if ((num.charAt(j) - '0') == i) { actualCount++; } } // If the counts don't match, return false. if (actualCount != expectedCount) { return false; } } // If all checks pass, return true. return true; }}Complexity
Time
O(n^2), where `n` is the length of the string `num`. The outer loop runs `n` times, and for each iteration, the inner loop also runs `n` times to count the occurrences.
Space
O(1), as we only use a few variables to store the counts and indices, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra data structures.
Cons
Inefficient for larger inputs due to the quadratic time complexity. However, it's acceptable for the given constraints (n <= 10).
A more efficient approach involves pre-calculating the frequency of each digit in the input string. We can use an array of size 10 to store the counts of digits 0 through 9. After a single pass to populate this frequency array, we can then iterate through the string again to check if the condition holds for each index.
Algorithm
- Create an integer array
countsof size 10, initialized to all zeros. This array will store the frequency of each digit from 0 to 9. - Iterate through the input string
numonce. For each charactercinnum:- Convert the character to its integer value:
digit = c - '0'. - Increment the count for this digit in the frequency array:
counts[digit]++.
- Convert the character to its integer value:
- After the first loop,
counts[d]will hold the total number of times digitdappears innum. - Iterate again from
i = 0ton-1, wherenis the length ofnum. - For each index
i:- Get the expected count from the string:
expectedCount = num.charAt(i) - '0'. - Get the actual count from our frequency array:
actualCount = counts[i]. - If
expectedCountis not equal toactualCount, returnfalse.
- Get the expected count from the string:
- If the second loop completes without returning
false, it means the condition is satisfied for all indices. Returntrue.
Walkthrough
This optimized approach avoids the redundant counting of the brute-force method by using a frequency array. It first makes a single pass through the string to count the occurrences of each digit and stores them in an array. Then, it makes a second pass to verify the condition for each index i by comparing the value num[i] with the pre-calculated count of digit i.
class Solution { public boolean digitCount(String num) { int n = num.length(); int[] counts = new int[10]; // First pass: count the frequency of each digit in the string. for (int i = 0; i < n; i++) { int digit = num.charAt(i) - '0'; counts[digit]++; } // Second pass: check if the condition holds for each index. for (int i = 0; i < n; i++) { // The digit i should appear num[i] times. int expectedCount = num.charAt(i) - '0'; // The actual count of digit i. int actualCount = counts[i]; if (actualCount != expectedCount) { return false; } } return true; }}Complexity
Time
O(n), where `n` is the length of the string `num`. We perform two separate passes over the string (or related to its length), each taking O(n) time. This results in a linear time complexity.
Space
O(1). We use a frequency array of size 10. Since the size of this array is constant and does not depend on the input size `n`, the space complexity is constant.
Trade-offs
Pros
More efficient with a linear time complexity.
Scales better for larger inputs compared to the brute-force approach.
Cons
Requires a small amount of extra space for the frequency array.
Solutions
Solution
class Solution {public boolean digitCount(String num) { int[] cnt = new int[10]; int n = num.length(); for (int i = 0; i < n; ++i) { ++cnt[num.charAt(i) - '0']; } for (int i = 0; i < n; ++i) { if (cnt[i] != num.charAt(i) - '0') { return false; } } return true; }}class Solution {public: bool digitCount(string num) { int cnt[10]{}; for (char &c : num) { ++cnt[c - '0']; } for (int i = 0; i < num.size(); ++i) { if (cnt[i] != num[i] - '0') { return false; } } return true; }};class Solution: def digitCount(self, num: str) -> bool: cnt = Counter(num) return all(cnt[str(i)] == int(v) for i, v in enumerate(num))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.