Leetcode 2283: Check if Number Has Equal Digit Count and Digit Value

Input: The input is a string `num` of length `n` consisting of digits, where 1 <= n <= 10.

Example: Input: num = "2020"

Constraints:

• 1 <= num.length <= 10

• num consists of digits.

Output: The output is a boolean value indicating whether the condition holds for every index.

Example: Output: true

Constraints:

Goal: The goal is to verify for each index `i` in the string `num`, the digit `i` must appear exactly `num[i]` times in the string.

Steps:

• Initialize an array to count the frequency of each digit.

• Iterate over each digit in the string and check if the frequency matches the expected value at that index.

• Return `true` if all conditions hold, otherwise return `false`.

Goal: The input string length is small, so the solution can handle all inputs efficiently.

Steps:

Assumptions:

• The string contains only digits.

• The length of the string will not exceed 10.

• Input: Input: num = "1210"

• Explanation: For this input, the conditions hold true because: num[0] = 1, and the digit 0 appears once in the string; num[1] = 2, and the digit 1 appears twice; num[2] = 1, and the digit 2 appears once; num[3] = 0, and the digit 3 appears zero times.

• Input: Input: num = "1122"

• Explanation: For this input, the condition fails because: num[0] = 1, and the digit 0 occurs zero times, which violates the condition.

Approach: The approach is to count the occurrences of each digit in the string and check if each digit at index `i` matches its expected frequency based on the digit value at `num[i]`.

Observations:

• We need to track the occurrences of digits efficiently.

• By iterating through the string and using a simple counting mechanism, we can verify if the condition holds for all indices.

Steps:

• Create an array `cnt` to track the frequency of each digit in the string.

• Iterate through the string and count occurrences of each digit.

• Check for each index `i` if the count of the digit at index `i` matches the value `num[i]`.

Empty Inputs:

• The input string is never empty, as the minimum length is 1.

Large Inputs:

• The maximum length of the input string is 10, so performance concerns are minimal.

Special Values:

• If the string consists of repeated zeros, the condition will fail if any index does not meet the expected count.

Constraints:

• The problem has a small input size, allowing us to use simple counting techniques.

bool digitCount(string num) {
int cnt[10] = {};
for (auto n : num)
    ++cnt[n - '0'];
for (int i = 0; i < num.size(); ++i)
    if (cnt[i] != num[i] - '0')
        return false;
return true;
}

1 : Function Declaration

bool digitCount(string num) {

The function `digitCount` takes a string `num` as input and returns a boolean value indicating whether the frequency of digits in `num` matches the digits at the respective positions.

2 : Initialize Count Array

int cnt[10] = {};

An array `cnt` of size 10 is initialized to 0. This array will be used to store the frequency of each digit (from 0 to 9) in the string `num`.

3 : Loop Through String

for (auto n : num)

This `for` loop iterates over each character in the string `num`, where each character represents a digit.

4 : Update Count Array

    ++cnt[n - '0'];

For each digit `n` in the string, we convert the character to its integer value (`n - '0'`) and increment the corresponding index in the `cnt` array.

5 : Loop Through Digits

for (int i = 0; i < num.size(); ++i)

This second `for` loop iterates over each index `i` of the string `num`, checking whether the frequency of the digit at position `i` matches the digit itself.

6 : Check Frequency Match

    if (cnt[i] != num[i] - '0')

This conditional checks if the frequency of digit `i` stored in `cnt[i]` matches the digit at position `i` in the string `num`. If they don't match, the function will return `false`.

7 : Return False

        return false;

If the frequencies do not match for any digit, the function returns `false` immediately, indicating the number doesn't satisfy the condition.

8 : Return True

return true;

If all digit frequencies match their respective digits, the function returns `true`, indicating that the number satisfies the condition.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where `n` is the length of the string, due to the single iteration over the string to count digits.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only need an array of size 10 to track the frequency of digits.

Leetcode 2283: Check if Number Has Equal Digit Count and Digit Value

Explore →