LeetCode 3908 - Valid Digit Number

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem is asking us to determine whether a given integer n is valid with respect to a digit x based on two conditions. First, n must contain at least one occurrence of the digit x. Second, n must not start with digit x. The input n is a non-negative integer up to 105, and x is a single digit from 0 to 9. The output is a Boolean value, true if both conditions are satisfied, otherwise false.

Restating in simpler terms, we are checking whether the number contains the digit somewhere after the first position.

Important edge cases include numbers with a single digit, numbers where x appears only as the first digit, numbers that do not contain x at all, and numbers where x is 0, since leading zeros are not represented in integer inputs. The constraints are small, so a simple conversion to string is feasible.

Approaches

The brute-force approach converts the number n to a string and iterates through each digit. It first checks if the first digit matches x. If it does, the number is immediately invalid. Otherwise, it scans the remaining digits for the presence of x. This is correct because it directly implements the problem conditions but involves iterating over the string representation of the number.

The optimal approach leverages the same idea but uses built-in string operations efficiently. By converting n to a string once, we can check the first character in constant time and use a membership test (in) to check the presence of x elsewhere. This approach avoids unnecessary loops and keeps the solution concise while still meeting the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(k)	Convert number to string, scan each digit
Optimal	O(k)	O(k)	Convert number to string, check first char and use `in` to check for presence

Here, k is the number of digits in n. Since n <= 105, k is at most 6, making the operation trivial.

Algorithm Walkthrough

Convert the integer n to its string representation s. This allows easy indexing and membership checking for digits.
Convert x to a string d because we will be comparing characters.
Check if the first character s[0] is equal to d. If it is, return false immediately because the number starts with x.
Check if d is present in the substring s[1:]. If it is, return true because the number contains x after the first digit.
If d is not found in s[1:], return false because the number does not contain x in a valid position.

Why it works: By isolating the first digit check and scanning only the remaining digits, we directly implement the two conditions in the problem statement. The first character check ensures the number does not start with x, while the membership test ensures that x occurs elsewhere in the number.

Python Solution

class Solution:
    def validDigit(self, n: int, x: int) -> bool:
        s = str(n)
        d = str(x)
        if s[0] == d:
            return False
        return d in s[1:]

In this implementation, we first convert n and x to strings. We check the first character explicitly, ensuring we do not accidentally accept numbers that start with x. Then we check the substring from the second character onward for x. This mirrors the algorithm exactly and handles single-digit and multi-digit numbers correctly.

Go Solution

import "strconv"

func validDigit(n int, x int) bool {
    s := strconv.Itoa(n)
    d := strconv.Itoa(x)
    if s[0:1] == d {
        return false
    }
    for i := 1; i < len(s); i++ {
        if string(s[i]) == d {
            return true
        }
    }
    return false
}

In Go, we convert integers to strings using strconv.Itoa. The first character check uses slicing. Since Go does not have a built-in in for strings, we manually iterate through the remaining characters to find a match. This ensures identical behavior to the Python solution.

Worked Examples

Example 1

Input: n = 101, x = 0

String conversion: s = "101", d = "0"

First character check: s[0] = "1" != "0" → proceed

Check remaining digits: "01"[0:] → contains "0" → return true

Example 2

Input: n = 232, x = 2

String conversion: s = "232", d = "2"

First character check: s[0] = "2" == "2" → return false

Example 3

Input: n = 5, x = 1

String conversion: s = "5", d = "1"

First character check: s[0] = "5" != "1" → proceed

Remaining digits: none → return false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	Convert to string and scan digits once, where k is the number of digits
Space	O(k)	Store string representation of number and digit

The algorithm is efficient for the constraints since n <= 105 and k <= 6.

Test Cases

sol = Solution()

assert sol.validDigit(101, 0) == True  # Example 1
assert sol.validDigit(232, 2) == False  # Example 2
assert sol.validDigit(5, 1) == False  # Example 3
assert sol.validDigit(10, 1) == False  # Starts with x
assert sol.validDigit(10, 0) == True  # Ends with x
assert sol.validDigit(0, 0) == False  # Single digit equal to x
assert sol.validDigit(123456, 6) == True  # x at the end
assert sol.validDigit(987654, 9) == False  # Starts with x

Test	Why
101, 0	Digit in middle, valid
232, 2	Starts with x, invalid
5, 1	Single digit, does not contain x, invalid
10, 1	Starts with x, invalid
10, 0	Ends with x, valid
0, 0	Single digit equal to x, invalid
123456, 6	x at end, valid
987654, 9	Starts with x, invalid

Edge Cases

The first important edge case is when n is a single digit. If n == x, the number is invalid because it starts with x and there are no other digits to satisfy the "contains" condition. The implementation handles this by first checking s[0].

The second edge case occurs when x = 0. Since leading zeros are impossible in integer representation, we only need to check for zeros appearing after the first digit. The algorithm correctly examines s[1:] for this.

The third edge case is when n contains multiple occurrences of x including the first digit. The first character check ensures we reject numbers starting with x, while the substring scan confirms the presence elsewhere does not matter if the number starts with x, which is correct according to the problem statement.