Scale Engineer

Check if Number Has Equal Digit Count and Digit Value

Easy
#2081Time: 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.2 companies
Patterns
Counting
Data structures
Hash TableString
Companies
J.P. MorganPornHub

Prompt

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.length
  • 1 <= n <= 10
  • num consists 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 num with an index i from 0 to n-1, where n is the length of the string.
  • For each index i, determine the expected count of the digit i. This is the integer value of the character num[i]. Let's call it expectedCount.
  • Initialize a counter actualCount to zero.
  • Start a nested loop to iterate through the string num again with an index j from 0 to n-1.
  • Inside the nested loop, check if the digit at num[j] is equal to the digit i.
  • If (num.charAt(j) - '0') == i, increment actualCount.
  • After the nested loop finishes, compare expectedCount with actualCount.
  • If expectedCount is not equal to actualCount, the condition is violated, so return false immediately.
  • 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).

Solutions

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

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.

← Previous

Previous problem

Next →

Next problem