Valid Digit Number solution and explanation
6 more videos on this problem
3908. Valid Digit Number (Leetcode Easy)Programming Live with Larry · 1:55 · 146 views
Valid Digit Number | Leetcode 3908 | Explanation With Code | Javacodewithsitaram · 12:05 · 41 views
Leetcode Biweekly Contest 181 | Valid Digit Number | Q1 | Leetcode 3908Pragya Gupta · 7:17 · 33 views
Valid Digit Number | LeetCode Biweekly Contest ExplainedSourav Coding Corner · 4:25 · 19 views
Valid Digit Number | Leetcode bi-weekly contest 181 | #3908UMANG AGRAWAL · 11:15 · 18 views
LeetCode Problem 3908 | Valid Digit NumberRepovive TV · 2:41 · 8 views
LeetCode 3908 | Valid Digit Number | Digit Check Explained | C++ SolutionPatel Jivan · 3:38 · 1 view
The problem
You are given an integer n and a digit x.
A number is considered valid if:
- It contains at least one occurrence of digit
x, and - It does not start with digit
x.
Return true if n is valid, otherwise return false.
Example 1:
Input: n = 101, x = 0
Output: true
Explanation:
The number contains digit 0 at index 1. It does not start with 0, so it satisfies both conditions. Thus, the answer is true.
Example 2:
Input: n = 232, x = 2
Output: false
Explanation:
The number starts with 2, which violates the condition. Thus, the answer is false.
Example 3:
Input: n = 5, x = 1
Output: false
Explanation:
The number does not contain digit 1. Thus, the answer is false.
Constraints:
0 <= n <= 1050 <= x <= 9
Approach overview
Problem Overview: Given a string, determine whether it represents a valid digit number. A valid digit number contains only characters from 0-9 and no letters, symbols, or whitespace.
Approach 1: Character-by-Character Validation (O(n) time, O(1) space)
Scan the string once and verify each character lies in the ASCII range for digits. During iteration, check whether '0' <= c <= '9'. The moment a non-digit appears, return false. This approach works well because digit validation is a constant-time comparison per character and requires no extra memory. It is the most common solution in interviews since it demonstrates clear understanding of string processing and basic character handling.
Approach 2: Built-in Digit Check (O(n) time, O(1) space)
Most languages expose helpers such as isdigit() or similar utilities. Iterate through the string and call the helper for each character. Internally these functions perform the same digit range check but provide cleaner syntax and fewer manual comparisons. This approach is slightly more readable while still maintaining linear runtime. It is useful when writing production code where readability matters more than demonstrating low-level logic.
Approach 3: Regular Expression Matching (O(n) time, O(1) space)
A concise alternative uses a regex pattern like ^[0-9]+$. The engine verifies that the entire string consists only of digits. Regex solutions are compact and expressive, especially when validation rules grow more complex. However, they introduce regex engine overhead and are usually less preferred in interviews unless the question explicitly involves regular expressions or string parsing.
Recommended for interviews: The character-by-character validation approach is typically expected. It shows you understand ASCII comparisons and can implement efficient single-pass validation. Mentioning the regex alternative demonstrates awareness of practical shortcuts, but the manual iteration solution signals stronger problem-solving fundamentals.
Solution
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 \texttt{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 \texttt{true} and n is not equal to x, then n is a valid number and we return \texttt{true}; otherwise, we return \texttt{false}.
The time complexity is O(log n), where n is the input integer. The space complexity is O(1).
class Solution:
def validDigit(self, n: int, x: int) -> bool:
has_x = False
while n > 9:
has_x = has_x or n % 10 == x
n //= 10
return has_x and n != xclass Solution {
public boolean validDigit(int n, int x) {
boolean hasX = false;
while (n > 9) {
hasX = hasX || (n % 10 == x);
n /= 10;
}
return hasX && (n != x);
}
}class Solution {
public:
bool validDigit(int n, int x) {
bool hasX = false;
while (n > 9) {
hasX = hasX || (n % 10 == x);
n /= 10;
}
return hasX && (n != x);
}
};function validDigit(n: number, x: number): boolean {
let hasX: boolean = false;
while (n > 9) {
hasX = hasX || n % 10 === x;
n = Math.floor(n / 10);
}
return hasX && n !== x;
}func validDigit(n int, x int) bool {
hasX := false
for n > 9 {
hasX = hasX || (n%10 == x)
n /= 10
}
return hasX && (n != x)
}impl Solution {
pub fn valid_digit(mut n: i32, x: i32) -> bool {
let mut has_x = false;
while n > 9 {
has_x = has_x || (n % 10 == x);
n /= 10;
}
has_x && (n != x)
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character-by-Character Validation | O(n) | O(1) | Best general solution for interviews and low-level validation |
| Built-in Digit Check (isdigit) | O(n) | O(1) | Cleaner production code when language helpers are available |
| Regular Expression Match | O(n) | O(1) | Concise validation when regex is already used in the codebase |
Frequently asked questions
Is Valid Digit Number easy or hard?
Valid Digit Number is typically classified as an easy problem. The main challenge is recognizing that a single linear scan with simple character checks is sufficient, resulting in an O(n) solution with constant memory.
Valid Digit Number Python/Java solution
In Python, iterate through the string and use c.isdigit() or compare against '0' and '9'. In Java, use Character.isDigit(c) inside a loop or perform ASCII comparisons. Both implementations run in O(n) time and constant space.
How to solve Valid Digit Number in O(n)?
Iterate through the string and validate each character using a range check such as '0' <= c <= '9'. If any character fails the check, return false immediately. If the loop finishes without violations, the string represents a valid digit number.
What is the best approach for Valid Digit Number?
The most reliable approach is scanning the string once and checking that every character lies between '0' and '9'. This single-pass validation runs in O(n) time and O(1) space. It avoids regex overhead and clearly demonstrates how digit validation works at the character level.
Is Valid Digit Number asked at Google/Amazon/Meta?
Digit validation and string parsing problems frequently appear in screening rounds because they test attention to detail and basic algorithm design. Variations of numeric validation appear in interviews at companies like Amazon and Google, often as part of larger parsing problems.
What data structure is used in Valid Digit Number?
The solution mainly relies on basic string traversal rather than complex data structures. The algorithm processes characters sequentially and performs constant-time comparisons, making it a straightforward string validation task.
What is the time complexity of Valid Digit Number?
All common solutions run in O(n) time where n is the length of the string. Each character must be inspected at least once to confirm it is a digit. Space complexity is O(1) because the algorithm only uses a few variables during iteration.