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.

Constraints:

• 0 <= n <= 100000
• 0 <= x <= 9

Examples:

• n = 323, x = 3 → False. It contains 3, but it also starts with 3.
• n = 132, x = 3 → True. It contains 3 and doesn't start with 3.
• n = 145, x = 3 → False. It doesn't contain 3 at all.

Walkthrough

String cast

We're using Python here so fortunately we can just cast the number to a string using str() then perform the checks. Don't forget to cast x to a string too when you're checking it.

1
2
3
4
5
6

class Solution:
  def validDigit(self, n: int, x: int) -> bool:
    digit_string = str(n)
    x_string = str(x)
    # Return True if both conditions pass.
    return digit_string[0] != x_string and x_string in digit_string

Submission result

It's important to double check the question. We can see that x and n are positive, so we don't need to worry about leading - signs.

In this solution, we end up scanning the first digit twice which is a minor inefficiency in practice. The problem states that n has at max 6 digits so this is a ~16% inefficiency. This feels large, but it is a theoretical count. In Python the overheads of the code running will make this insignificant in practice.

However, the most important thing in the solution is that the first digit check is first. This is a O(1) check so we do that first. If the test input numbers are evenly distributed then ~10% of them will exit on this cheap check, and the more expensive scan of the remaining characters will be skipped. The important thing to note there is the right side of the and isn't executed if the left side is False. This is called short-circuit evaluation.

The time is dominated by iterating over the digit_string. In the worst case we have to look over the whole string so it's linear complexity O(d) where d is the number of digits in n.

No string cast

Not all languages are as nice as Python giving you the str() function to make this trivial. The interviewer may ask you to solve this without using str().

To do this we must use a mathematical approach using integer arithmetic on the values instead. We can extract the last digit by taking value % 10 and use this to walk along making sure we keep track of the last digit we see so we can finish with the leading digit check.

This is nice because we get the leading digit for free. Each pass of the loop strips one digit off the right with n //= 10, so the very last value digit takes before n hits 0 is the most significant digit of the original number!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def validDigit(self, n: int, x: int) -> bool:
    found_digit = False
    # Any non-zero `n` is truthy; loop ends at 0.
    while n:
      digit = n % 10
      # Mark if we've found our target digit
      if digit == x:
        found_digit = True
      # Move onto next digit
      n //= 10
    # After we've finished we can do the check on the first digit.
    return found_digit and digit != x

Submission result

An important edge case to consider here is n = 0. This will not execute the while loop, so it can never be True. But that's okay because no single digit number can both not start with and contain the target x so these will always be invalid.

Indeed the code handles this because found_digit = False at the start, so the return found_digit and digit != x short-circuits on the left side and never evaluates digit (which would be undefined).

This is the same complexity as the other solution at O(d).