algoadvance

Problem Statement

You need to determine if a number is “fascinating.” A number is considered fascinating if, when concatenated with its double and triple, the result contains all digits from 1 to 9 exactly once and does not contain the digit 0.

Clarifying Questions

  1. Are there any constraints on the input number (e.g., its range)?
  2. Is leading zero considered in the digits?
  3. Should we handle any special cases like negative numbers or non-integer inputs?

For simplification, let’s assume the input number is a positive integer and we need to check it directly as described.

Strategy

  1. First, generate the concatenated string by combining the input number, its double, and its triple.
  2. Then, check if this string contains all digits from 1 to 9 exactly once.

Steps

  1. Convert the number to a string.
  2. Concatenate the string representations of n, 2 * n, and 3 * n.
  3. Check if the concatenated string has exactly 9 characters.
  4. Verify that this string contains all digits from ‘1’ to ‘9’ and does not contain ‘0’.

Pseudocode

function isFascinating(n):
    concatenated = str(n) + str(2*n) + str(3*n)
    if length of concatenated is not 9:
        return False
    required_digits = set('123456789')
    return set(concatenated) == required_digits

Now, let’s write the Python code for this.

Code

def is_fascinating(n: int) -> bool:
    concatenated = str(n) + str(2 * n) + str(3 * n)
    if len(concatenated) != 9:
        return False
    required_digits = set('123456789')
    return set(concatenated) == required_digits

# Example Usage
print(is_fascinating(192))  # True
print(is_fascinating(100))  # False

Time Complexity

The time complexity of this approach is O(1) because:

  1. The operations we perform (concatenation, length check, and set comparison) all operate over a fixed-size string of length 9, which does not scale with the size of the input number.
  2. The set operations and string manipulations are constant time due to the fixed size of the data.

This ensures that our solution is efficient and operates in constant time relative to the input size.

Try our interview co-pilot at AlgoAdvance.com