algoadvance

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

Problem Statement

The problem is as follows:

You are given a string num consisting of digits. Return true if for every digit d in the string num, the digit d appears d times in the string. Otherwise, return false.

For example, given the string "1210", the number 1 in the 0th index of the string appears 1 time(s) in the string, the number 2 in the 1st index appears 2 time(s) in the string, the number 1 in the 2nd index appears 1 time(s) in the string, and the number 0 in the 3rd index appears 0 time(s) in the string. Since the counts align with the values, the output should be true for "1210".

Clarifying Questions

  1. Constraints on the input string (length, characters)?
    • The string will only contain digits and will have a length between 1 and 10 inclusive.
  2. Should we consider leading zeros or other invalid digit scenarios?
    • The string will be a valid digit string as per the usual constraints of the problem.

Strategy

  1. Initialize a Counter: Create an array of size 10 (for digits 0 through 9) to keep count of how many times each digit appears in the string.
  2. Count Digits: Iterate over the input string and update the counter for each digit.
  3. Check Conditions: Iterate over the string again and check if the digit d at position i appears exactly d times in the string.
  4. Return the Result: If all conditions are satisfied, return true. Otherwise, return false.

Code

#include <iostream>
#include <vector>
#include <string>

bool digitCount(std::string num) {
    std::vector<int> count(10, 0); // Array to count occurrences of each digit
    
    // Count occurrences of each digit
    for (char c : num) {
        count[c - '0']++;
    }
    
    // Check if the digit count matches the expected value
    for (int i = 0; i < num.size(); i++) {
        int digit = num[i] - '0';
        if (count[i] != digit) {
            return false;
        }
    }
    
    return true;
}

int main() {
    std::string num = "1210";
    std::cout << std::boolalpha << digitCount(num) << std::endl; // Output: true
    
    num = "030";
    std::cout << std::boolalpha << digitCount(num) << std::endl; // Output: false
    
    return 0;
}

Time Complexity

Thus, the total time complexity is O(n).

Space Complexity

The space complexity is O(1) as we are using a fixed-size array (of size 10) regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI