3908. Valid Digit Number

EasyMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n and a digit x.

A number is considered valid if it satisfies both of the following conditions:

It contains at least one occurrence of the digit x, and
It does not start with the digit x.

Your task is to determine whether the given integer n meets these two conditions.

Return true if n is valid; otherwise, return false.

In other words, the digit x must appear somewhere within n, but it cannot be the leading (first/most significant) digit of n.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

A mathematical formula or identity computes the answer directly.

Open in Flowchart

Intuition

To check whether n is valid, we need to verify two things: whether the digit x appears somewhere in n, and whether x is not the leading digit.

A natural way to inspect each digit of a number is to repeatedly look at its last digit using the modulo operation n % 10, and then remove that digit using integer division n //= 10. By doing this in a loop, we can examine every digit from right to left.

The key observation is how to separate the leading digit from the rest. When we keep dividing n by 10, the moment n becomes a single digit (n <= 9), that remaining value is exactly the leading digit of the original number. So we can loop while n > 9, checking each of the lower digits against x, and once the loop ends, the value left in n is the leading digit.

With this idea, we use a boolean variable hasX to track whether x shows up among all the non-leading digits during the loop. After the loop, we simply check two conditions together: hasX must be true (meaning x appeared in the lower digits, which also guarantees x is not the leading digit since we never counted the leading digit), and the leading digit n must not equal x. If both hold, n is valid.

This neatly handles both requirements at once — the loop naturally excludes the leading digit from the hasX check, so any occurrence of x we find is guaranteed to be in a non-leading position, and the final comparison ensures the leading digit itself isn't x.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Simulation

We use a boolean variable hasX to record whether the digit x appears in n.

We repeatedly take the last digit of n and compare it with x. If they are equal, we set hasX to true. At the same time, we divide n by 10 to remove the last digit. When n is less than or equal to 9, it means we have checked all the digits. At this point, if hasX is true and n is not equal to x, then n is a valid number and we return true; otherwise, we return false.

The implementation details are as follows:

Initialize hasX = False to track whether x has been found among the non-leading digits.
Loop while n > 9:
- Update hasX using hasX = hasX or n % 10 == x, which checks if the current last digit equals x.
- Remove the last digit with n //= 10.
After the loop, n holds the leading digit. Return hasX and n != x.

The time complexity is O(log n), where n is the given integer, since the number of digits in n is proportional to log n. The space complexity is O(1), as we only use a constant amount of extra space.

Example Walkthrough

Let's trace through a small example with n = 253 and x = 3.

We want to check two things: does the digit 3 appear somewhere in 253, and is 3 not the leading digit? Looking at 253, the digit 3 does appear (as the last digit), and the leading digit is 2 (not 3), so we expect the answer to be true. Let's confirm this with the algorithm.

Initial state:

n = 253, x = 3
hasX = False

Iteration 1: (n = 253, which is > 9, so we enter the loop)

Look at the last digit: n % 10 = 253 % 10 = 3.
Compare with x: 3 == 3 is True, so we update hasX = False or True = True.
Remove the last digit: n //= 10 makes n = 25.

Iteration 2: (n = 25, which is > 9, so we continue)

Look at the last digit: n % 10 = 25 % 10 = 5.
Compare with x: 5 == 3 is False, so hasX = True or False = True (stays True).
Remove the last digit: n //= 10 makes n = 2.

Loop ends: (n = 2, which is <= 9, so we stop)

At this point, the value left in n is 2, which is exactly the leading digit of the original number 253. Notice that the loop never examined this leading digit against x, so the hasX flag only reflects occurrences of x among the non-leading digits.

Final check: Return hasX and n != x:

hasX is True (the digit 3 was found among the lower digits).
n != x is 2 != 3, which is True (the leading digit is not 3).
Result: True and True = True.

So the function returns true, confirming that 253 is valid.

A quick contrasting case: consider n = 35 and x = 3. Here 3 is the leading digit, which should make it invalid.

n = 35 > 9: last digit is 5, 5 == 3 is False, so hasX stays False; n becomes 3.
Loop ends since n = 3 <= 9. The leading digit is 3.
Return hasX and n != x → False and (3 != 3) → False and False = False.

The function correctly returns false, because the only occurrence of 3 was in the leading position, which the loop deliberately excluded from hasX.

Solution Implementation

1class Solution:
2    def validDigit(self, n: int, x: int) -> bool:
3        # Tracks whether digit `x` appears in any position
4        # other than the most significant (leftmost) digit.
5        found_in_lower_digits: bool = False
6
7        # Strip off digits from the right while more than one digit remains.
8        # This loop intentionally skips the leftmost digit, which is left in `n`.
9        while n > 9:
10            # Check the current least-significant digit against `x`.
11            found_in_lower_digits = found_in_lower_digits or (n % 10 == x)
12            n //= 10  # Remove the processed digit.
13
14        # `n` now holds the most significant digit.
15        # Valid only if `x` appears in lower digits AND is NOT the leading digit.
16        return found_in_lower_digits and n != x
17```
18
19## Notes on Changes
20
21- **Naming**: Renamed `has_x` to `found_in_lower_digits` to clarify it only reflects non-leading digit matches.
22- **Type hints**: Added `: bool` annotation for the local variable, consistent with Python 3 style.
23- **Comments**: Explained the loop's intentional skipping of the leading digit and the final two-part condition.
24- **Method name**: Kept `validDigit` unchanged as requested.
25
26## Alternative Perspective
27
28If the original intent was actually to check whether `x` appears **anywhere** in `n` (a more common requirement), the logic would need a fix, since the current version misses the leading digit. A version that checks all digits would be:
29
30```python3
31class Solution:
32    def validDigit(self, n: int, x: int) -> bool:
33        # Returns True if digit `x` appears anywhere in `n`.
34        while n > 0:
35            if n % 10 == x:
36                return True
37            n //= 10
38        return False
39

1class Solution {
2    /**
3     * Checks whether the given target digit appears among the non-leading
4     * digits of the number, while the leading (most significant) digit
5     * is NOT equal to the target digit.
6     *
7     * @param number      the integer to inspect
8     * @param targetDigit the digit (0-9) we are searching for
9     * @return true if targetDigit occurs in a non-leading position
10     *         and the leading digit differs from targetDigit
11     */
12    public boolean validDigit(int number, int targetDigit) {
13        // Flag indicating whether targetDigit was found in any non-leading digit
14        boolean containsDigit = false;
15
16        // Iterate while more than one digit remains, so the loop
17        // examines every digit except the leading one.
18        while (number > 9) {
19            // Compare the current least-significant digit with targetDigit
20            containsDigit = containsDigit || (number % 10 == targetDigit);
21            // Remove the processed digit
22            number /= 10;
23        }
24
25        // At this point 'number' is the leading digit.
26        // Return true only if targetDigit was found among the trailing digits
27        // AND the leading digit is not equal to targetDigit.
28        return containsDigit && (number != targetDigit);
29    }
30}
31

1class Solution {
2public:
3    // Returns true if `targetDigit` appears among the non-leading digits
4    // of `number`, but is NOT the leading (most-significant) digit.
5    bool validDigit(int number, int targetDigit) {
6        const int kMaxSingleDigit = 9;  // boundary to detect the leading digit
7        bool foundInTrailing = false;   // tracks if targetDigit appears in trailing digits
8
9        // Process every digit except the most-significant one.
10        // The loop stops when `number` is reduced to a single digit (the leading digit).
11        while (number > kMaxSingleDigit) {
12            int currentDigit = number % 10;                     // extract the last digit
13            foundInTrailing = foundInTrailing || (currentDigit == targetDigit);
14            number /= 10;                                       // drop the last digit
15        }
16
17        // `number` now holds the leading digit.
18        // Require: targetDigit found in trailing digits AND leading digit differs from it.
19        return foundInTrailing && (number != targetDigit);
20    }
21};
22

1/**
2 * Checks whether the given digit appears in `num`, but only among its
3 * non-leading digits, while the leading (most significant) digit is NOT
4 * equal to the target digit.
5 *
6 * @param num   The number to inspect.
7 * @param digit The target digit (0-9) to search for.
8 * @returns     True if `digit` is found in any position except the leading
9 *              one, and the leading digit differs from `digit`; otherwise false.
10 */
11function validDigit(num: number, digit: number): boolean {
12    // Flag indicating whether the target digit was found among non-leading digits.
13    let hasDigit: boolean = false;
14
15    // Process every digit except the leading one.
16    // The loop stops once `num` is reduced to a single digit (num <= 9),
17    // leaving `num` holding the leading digit.
18    while (num > 9) {
19        // Check the current least-significant digit against the target.
20        hasDigit = hasDigit || num % 10 === digit;
21        // Drop the least-significant digit.
22        num = Math.floor(num / 10);
23    }
24
25    // Return true only if the digit was found in a non-leading position
26    // AND the leading digit is not equal to the target digit.
27    return hasDigit && num !== digit;
28}
29

Time and Space Complexity

Time Complexity: O(log n), where n is the input integer. The while loop repeatedly divides n by 10 (n //= 10) until n becomes a single digit (i.e., n <= 9). Since each iteration removes one decimal digit, the number of iterations equals the number of digits in n, which is approximately log₁₀(n). Therefore, the time complexity is O(log n).
Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables has_x, n, and x, regardless of the size of the input. No additional data structures that scale with the input are allocated.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misusing the loop condition n > 9 and accidentally checking the leading digit

A frequent mistake is changing the loop condition from while n > 9 to while n > 0 while keeping the rest of the simulation logic intact. The original code deliberately stops when a single digit remains so that the leftmost (leading) digit is excluded from the found_in_lower_digits check. If you switch to while n > 0, the leading digit also gets compared against x, which corrupts the result:

# WRONG: leading digit is now included in the search
while n > 0:
    found_in_lower_digits = found_in_lower_digits or (n % 10 == x)
    n //= 10
return found_in_lower_digits and n != x  # n is now 0, so `n != x` is meaningless

After this loop, n becomes 0, so the final check n != x no longer represents the leading digit. The condition silently breaks.

Solution: Keep the loop bounded by while n > 9 so the leading digit is preserved in n for the final comparison, exactly as the original code does.

Pitfall 2: Forgetting the single-digit edge case

When n is a single digit (e.g., n = 5), the while n > 9 loop never executes. In that situation:

found_in_lower_digits stays False,
the only digit is the leading digit.

The return found_in_lower_digits and n != x correctly yields False, because a one-digit number can never have x in a non-leading position. The pitfall is assuming a single-digit n equal to x should return True—it must not, since x would be the leading digit.

Solution: No special-casing is needed; the existing found_in_lower_digits flag (initialized to False) naturally handles this. Just be careful not to "fix" it by adding a spurious n == x check.

Pitfall 3: Confusing "contains anywhere" with "contains in a non-leading position"

This is the most conceptually dangerous trap. Many similar problems simply ask whether digit x appears anywhere in n. Here, the leading digit is explicitly disallowed as a match. Reusing a generic "digit exists in number" template will produce wrong answers for inputs like n = 35, x = 3, where x appears only as the leading digit (expected False, but a generic checker returns True).

Solution: Read the constraint carefully. The leading digit occurrence must be ignored. The structure—loop over all digits except the last-remaining (leading) one, then verify n != x—correctly enforces both conditions in a single pass.

Pitfall 4: Negative numbers

If n could be negative, n % 10 and n //= 10 behave differently in Python due to floor division toward negative infinity (e.g., -35 % 10 == 5, -35 // 10 == -4). This would cause incorrect digit extraction and a loop that never terminates correctly.

Solution: If negative inputs are possible per the constraints, normalize first with n = abs(n) before entering the loop. If the constraints guarantee n is a positive integer, this can be safely ignored.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know