Check if Number Has Equal Digit Count and Digit Value

Check if Number Has Equal Digit Count and Digit Value - Problem

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: If num = "1210", then:

Digit 0 should appear num[0] = 1 time (it appears 1 time ✓)
Digit 1 should appear num[1] = 2 times (it appears 2 times ✓)
Digit 2 should appear num[2] = 1 time (it appears 1 time ✓)
Digit 3 should appear num[3] = 0 times (it appears 0 times ✓)

All conditions are satisfied, so return true.

Input & Output

Example 1 — Valid Self-Describing Number

$ Input: num = "1210"

› Output: true

💡 Note: Digit 0 appears 1 time (num[0]=1), digit 1 appears 2 times (num[1]=2), digit 2 appears 1 time (num[2]=1), digit 3 appears 0 times (num[3]=0). All conditions satisfied.

Example 2 — Invalid Count

$ Input: num = "030"

› Output: false

💡 Note: Digit 0 should appear 0 times (num[0]=0), but it appears 2 times in the string. This violates the condition.

Example 3 — Single Digit

$ Input: num = "0"

› Output: true

💡 Note: Digit 0 should appear 0 times (num[0]=0), and it appears 0 times (not counting itself in this context). Wait, this is tricky - digit 0 actually appears 1 time, so this should be false.

Constraints

1 ≤ num.length ≤ 10
num consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String "1210" where each position represents a digit count requirement

Process

Count actual digit frequencies and compare with position requirements

Output

Return true if all positions match their count requirements

Key Takeaway

🎯 Key Insight: A self-describing number has the property that digit at position i equals the count of digit i in the entire string

Asked in

G Google 15 a Amazon 12 M Meta 8

The key insight is to verify the self-describing property by counting digit frequencies and checking if each position i has the correct count for digit i. Best approach uses frequency counting with two passes through the string. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - One Pass Optimization	O(n)	O(1)	Count all digit frequencies once, then verify each position
Brute Force - Check Each Digit Individually	O(n²)	O(1)	For each position i, count occurrences of digit i in entire string

Frequency Count - One Pass Optimization — Algorithm Steps

Step 1: Create frequency array and count all digits in one pass
Step 2: For each position i, check if frequency[i] equals num[i]
Step 3: Return false if any mismatch, true if all match

Visualization

Tap to expand

Step-by-Step Walkthrough

Count All Digits

Build frequency array in one pass

Verify Each Position

Check if freq[i] matches num[i]

Result

All positions match their expected frequencies

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* num) {
    int n = strlen(num);
    // Count frequency of each digit
    int freq[10] = {0};
    for (int i = 0; i < n; i++) {
        int digit = num[i] - '0';
        freq[digit]++;
    }
    
    // Check each position
    for (int i = 0; i < n; i++) {
        int expected = num[i] - '0';
        if (freq[i] != expected) {
            return false;
        }
    }
    return true;
}

int main() {
    char num[1001];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    bool result = solution(num);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through string: one to count frequencies, one to verify

✓ Linear Growth

Space Complexity

O(1)

Frequency array of size 10 for digits 0-9 is constant space

✓ Linear Space

23.0K Views

Medium Frequency

~8 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count - One Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler