Jobs

Interviews

Discussions

Check if Number Has Equal Digit Count and Digit Value

Easy

Asked by:

23 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Check if Number Has Equal Digit Count and Digit Value

Easy

Asked by:

23 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the input number? Specifically, is it a string or an integer?
Are there any constraints on the size (number of digits) of the input number?
If the input number does not satisfy the condition (equal digit count and digit value), what should the function return? Should I return null, false, or throw an exception?
Are all digits from 0-9 guaranteed to be present in the input number, or can some digits be missing?
Could you provide an example of an input number that *does* satisfy the condition to ensure my understanding is correct?

Brute Force Solution

Approach

The brute force approach systematically checks if a number meets the specified digit count criteria. It involves counting how many times each digit appears and then comparing those counts to the actual digits in the original number.

Here's how the algorithm would work step-by-step:

First, figure out how many times each digit (0 through 9) shows up in the number.
Then, for each digit position in the number, check if the digit at that position matches the count you found for that digit.
If all the digit counts match the digits in their corresponding positions, then the number meets the requirement. Otherwise, it doesn't.

Code Implementation

def check_equal_digit_count_and_value(number):
    number_string = str(number)
    number_length = len(number_string)

    # Count occurrences of each digit
    digit_counts = [0] * 10
    for digit_char in number_string:
        digit = int(digit_char)
        digit_counts[digit] += 1

    # Compare digit counts with digit values at each index
    for index in range(number_length):
        digit_at_index = int(number_string[index])

        # Check if count of digit at index equals the digit at index
        if digit_counts[index] != digit_at_index:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the number, which has n digits where n is the length of the number's string representation, to count the occurrences of each digit (0-9). Then, it iterates through the number again, comparing each digit to the previously calculated count of that digit. Because we have two iterations of a single loop related to the number's size, the time complexity is O(n) as opposed to O(n*10) because the 10 is referring to the number of digit possibilities and will not scale with n.

Space Complexity

O(1) – The described solution primarily utilizes a digit count array to store the frequency of each digit (0-9). This array has a fixed size of 10, independent of the input number's size, N. Therefore, the auxiliary space used remains constant regardless of the input, and does not scale with the size of the input number. No other significant data structures or recursive calls are involved.

Optimal Solution

Approach

The goal is to verify if each digit in a number appears as many times as the digit's own value. We can accomplish this by counting the occurrences of each digit and then comparing those counts to the digits themselves.

Here's how the algorithm would work step-by-step:

First, count how many times each digit, from zero to nine, appears in the number.
Then, for each digit, compare its count to the actual digit itself. For example, if the digit '3' appears three times, that part is correct.
If the count of every digit matches the digit's value, then the number satisfies the requirement. Otherwise, it doesn't.

Code Implementation

def check_equal_digit_count_and_digit_value(number):
    number_string = str(number)
    number_length = len(number_string)
    digit_counts = [0] * 10

    for digit_char in number_string:
        digit = int(digit_char)
        digit_counts[digit] += 1

    # Iterate through each digit and compare count to value.
    for index in range(number_length):
        digit = int(number_string[index])

        #Checking that digit's count matches the digit's value
        if digit_counts[index] != digit:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input string once to count the frequency of each digit. This takes O(n) time, where n is the length of the input string. Then, we iterate a fixed number of times (10 times, to check digits 0-9) to compare the counts with the digit values. Since the second loop has a constant bound, the overall time complexity is dominated by the first loop, resulting in O(n).

Space Complexity

O(1) – The algorithm requires storing a count for each digit from 0 to 9. This can be implemented using an array or a hash map of fixed size 10, which is independent of the size of the input number. Therefore, the auxiliary space used is constant, irrespective of the input size N (where N is the number of digits in the input number). Hence the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return true if the string is null or empty, as the condition is trivially satisfied with no digits.
String with length greater than 10 (exceeding possible digit values)	Return false immediately, since the string length restricts possible digit values to 0-9.
String contains characters other than digits 0-9	Throw an IllegalArgumentException or return false since the input must be a string of digits.
String where all digits are 0	Check if the count of 0s matches '0's digit value's index; return accordingly.
String where all digits are same but not 0	Check if the count of that digit equals its place in the string; return accordingly.
String with a very large number of 0s relative to other digits	The counting mechanism will appropriately handle this case.
String representing a single digit number	Check if the digit itself matches its place (index 0), returning true if they are the same.
Input String such that some digit has a count equal to the String's length	This should be properly handled by the counting approach and return either True or False based on if all other digit counts match.

Null or empty string input

How to Handle:

Return true if the string is null or empty, as the condition is trivially satisfied with no digits.

String with length greater than 10 (exceeding possible digit values)

How to Handle:

Return false immediately, since the string length restricts possible digit values to 0-9.

String contains characters other than digits 0-9

How to Handle:

Throw an IllegalArgumentException or return false since the input must be a string of digits.

String where all digits are 0

How to Handle:

Check if the count of 0s matches '0's digit value's index; return accordingly.

String where all digits are same but not 0

How to Handle:

Check if the count of that digit equals its place in the string; return accordingly.

String with a very large number of 0s relative to other digits

How to Handle:

The counting mechanism will appropriately handle this case.

String representing a single digit number

How to Handle:

Check if the digit itself matches its place (index 0), returning true if they are the same.

Input String such that some digit has a count equal to the String's length

How to Handle:

This should be properly handled by the counting approach and return either True or False based on if all other digit counts match.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the input number? Specifically, is it a string or an integer?
Are there any constraints on the size (number of digits) of the input number?
If the input number does not satisfy the condition (equal digit count and digit value), what should the function return? Should I return null, false, or throw an exception?
Are all digits from 0-9 guaranteed to be present in the input number, or can some digits be missing?
Could you provide an example of an input number that *does* satisfy the condition to ensure my understanding is correct?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out how many times each digit (0 through 9) shows up in the number.
Then, for each digit position in the number, check if the digit at that position matches the count you found for that digit.
If all the digit counts match the digits in their corresponding positions, then the number meets the requirement. Otherwise, it doesn't.

Code Implementation

def check_equal_digit_count_and_value(number):
    number_string = str(number)
    number_length = len(number_string)

    # Count occurrences of each digit
    digit_counts = [0] * 10
    for digit_char in number_string:
        digit = int(digit_char)
        digit_counts[digit] += 1

    # Compare digit counts with digit values at each index
    for index in range(number_length):
        digit_at_index = int(number_string[index])

        # Check if count of digit at index equals the digit at index
        if digit_counts[index] != digit_at_index:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each digit, from zero to nine, appears in the number.
Then, for each digit, compare its count to the actual digit itself. For example, if the digit '3' appears three times, that part is correct.
If the count of every digit matches the digit's value, then the number satisfies the requirement. Otherwise, it doesn't.

Code Implementation

def check_equal_digit_count_and_digit_value(number):
    number_string = str(number)
    number_length = len(number_string)
    digit_counts = [0] * 10

    for digit_char in number_string:
        digit = int(digit_char)
        digit_counts[digit] += 1

    # Iterate through each digit and compare count to value.
    for index in range(number_length):
        digit = int(number_string[index])

        #Checking that digit's count matches the digit's value
        if digit_counts[index] != digit:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true if the string is null or empty, as the condition is trivially satisfied with no digits.
String with length greater than 10 (exceeding possible digit values)	Return false immediately, since the string length restricts possible digit values to 0-9.
String contains characters other than digits 0-9	Throw an IllegalArgumentException or return false since the input must be a string of digits.
String where all digits are 0	Check if the count of 0s matches '0's digit value's index; return accordingly.
String where all digits are same but not 0	Check if the count of that digit equals its place in the string; return accordingly.
String with a very large number of 0s relative to other digits	The counting mechanism will appropriately handle this case.
String representing a single digit number	Check if the digit itself matches its place (index 0), returning true if they are the same.
Input String such that some digit has a count equal to the String's length	This should be properly handled by the counting approach and return either True or False based on if all other digit counts match.

Null or empty string input

How to Handle:

Return true if the string is null or empty, as the condition is trivially satisfied with no digits.

String with length greater than 10 (exceeding possible digit values)

How to Handle:

Return false immediately, since the string length restricts possible digit values to 0-9.

String contains characters other than digits 0-9

How to Handle:

Throw an IllegalArgumentException or return false since the input must be a string of digits.

String where all digits are 0

How to Handle:

Check if the count of 0s matches '0's digit value's index; return accordingly.

String where all digits are same but not 0

How to Handle:

Check if the count of that digit equals its place in the string; return accordingly.

String with a very large number of 0s relative to other digits

How to Handle:

The counting mechanism will appropriately handle this case.

String representing a single digit number

How to Handle:

Check if the digit itself matches its place (index 0), returning true if they are the same.

Input String such that some digit has a count equal to the String's length

How to Handle:

This should be properly handled by the counting approach and return either True or False based on if all other digit counts match.