Problem Description

You are given a 3-digit integer n (a number between 100 and 999).

A number is called fascinating if it meets a specific condition after performing the following steps:

1. Calculate 2 * n and 3 * n
2. Concatenate the three numbers together: n, 2 * n, and 3 * n (join them as a string, one after another)
3. Check if the resulting concatenated number contains each digit from 1 to 9 exactly once, with no 0's present

Your task is to determine whether the given number n is fascinating or not. Return true if it is fascinating, false otherwise.

Example walkthrough:

• If n = 192
• Then 2 * n = 384 and 3 * n = 576
• Concatenating gives us: 192384576
• This contains the digits 1, 2, 3, 4, 5, 6, 7, 8, 9 exactly once each
• No zeros are present
• Therefore, 192 is a fascinating number

Solution Explanation: The solution concatenates n, 2*n, and 3*n into a single string s. It then sorts all the characters in this string and checks if the sorted result equals "123456789". If the sorted string matches exactly, it means we have each digit from 1-9 appearing exactly once, making the number fascinating.

Intuition

The key insight is recognizing that we need to verify two conditions: the concatenated string must contain exactly the digits 1-9, with each appearing once, and no zeros.

When we concatenate n, 2*n, and 3*n, we get a string of digits. To check if this string contains each digit from 1 to 9 exactly once, we could:

1. Count the frequency of each digit and verify each appears exactly once
2. Check the length is exactly 9 and verify no duplicates exist
3. Sort the string and compare it to a known pattern

The third approach is the most elegant. If we sort all the characters in our concatenated string, and it contains exactly one of each digit from 1-9, then the sorted result must be "123456789". This single comparison handles all our requirements:

• If there's a 0, the sorted string would start with "0"
• If any digit is missing, the string would be too short
• If any digit appears more than once, the string would be too long or have duplicates
• If the string has exactly the digits 1-9 once each, sorting will produce exactly "123456789"

This transforms our complex validation problem into a simple string comparison after sorting, making the solution both concise and efficient.

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward approach:

1. String Concatenation: First, we convert n and its multiples to strings and concatenate them:

   s = str(n) + str(2 * n) + str(3 * n)

   This creates a single string containing all digits from n, 2*n, and 3*n in sequence.

2. Sorting the String: We sort all characters in the concatenated string:

   sorted(s)

   This returns a list of characters in ascending order. For example, if s = "192384576", sorting gives us ['1', '2', '3', '4', '5', '6', '7', '8', '9'].

3. Join and Compare: We join the sorted characters back into a string and compare with the target pattern:

   "".join(sorted(s)) == "123456789"

   The join() method converts the sorted list back to a string. If this equals "123456789", we know that:

   • The string has exactly 9 characters
   • Each digit from 1-9 appears exactly once
   • No zeros are present (otherwise the sorted string would start with "0")

The entire check is done in a single line, making the solution both elegant and efficient. The time complexity is O(1) since we're always dealing with a fixed-size string (9 characters), and the space complexity is also O(1) for the same reason.

Example Walkthrough

Let's walk through the solution with n = 192:

Step 1: Calculate multiples

• n = 192
• 2 * n = 384
• 3 * n = 576

Step 2: Concatenate the numbers

• Convert each to string: "192", "384", "576"
• Concatenate them: s = "192384576"

Step 3: Sort the concatenated string

• Break s into individual characters: ['1', '9', '2', '3', '8', '4', '5', '7', '6']
• Sort them: ['1', '2', '3', '4', '5', '6', '7', '8', '9']

Step 4: Join and compare

• Join the sorted characters: "123456789"
• Compare with target: "123456789" == "123456789" → True

Since the sorted string exactly matches "123456789", we confirm that 192 is a fascinating number.

Counter-example with n = 123:

• 2 * n = 246, 3 * n = 369
• Concatenated: s = "123246369"
• Sorted: "122334669"
• Compare: "122334669" != "123456789" → False

The sorted string doesn't match because we have duplicate digits (2, 3, 6 appear twice) and missing digits (5, 7, 8), so 123 is not fascinating.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The time complexity breaks down as follows:

• Converting n, 2*n, and 3*n to strings: O(log n) for each conversion, but since n is bounded (must be a 3-digit number to create a 9-digit concatenation), this is effectively O(1)
• String concatenation: O(1) since we're concatenating exactly 3 strings of fixed length (3 digits each)
• Sorting the 9-character string: O(k log k) where k = 9, which is O(1)
• String comparison: O(1) for comparing two 9-character strings

Since all operations work on fixed-size data (9 characters), the overall time complexity is O(1).

Space Complexity: O(1)

The space complexity analysis:

• String s stores exactly 9 characters: O(1)
• The sorted string creates a new string of 9 characters: O(1)
• Temporary variables for multiplication and string conversion: O(1)

All space usage is constant regardless of the input value (as long as it's a valid 3-digit number), resulting in O(1) space complexity.

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

Common Pitfalls

1. Not Handling Edge Cases with Leading Zeros

While the current solution works correctly, a common mistake when solving this problem is trying to optimize by checking the length first or using set operations without considering all requirements:

Incorrect Approach:

def isFascinating(self, n: int) -> bool:
    s = str(n) + str(2 * n) + str(3 * n)
    return len(s) == 9 and set(s) == set("123456789")

Why it fails: This approach using sets would incorrectly accept numbers that have duplicate digits as long as all digits 1-9 are present. For example, if the concatenation was "112345679", the set would still contain all required digits, but it's not a valid fascinating number.

2. Integer Overflow Concerns in Other Languages

If implementing this in languages with fixed integer sizes, concatenating as integers rather than strings could cause overflow:

Problematic Approach (in concept):

def isFascinating(self, n: int) -> bool:
    # Trying to concatenate as numbers instead of strings
    concatenated = n * 1000000 + (2 * n) * 1000 + (3 * n)
    # Then check digits...

Solution: Always use string concatenation for this problem to avoid numerical overflow and maintain simplicity.

3. Forgetting About the Zero Constraint

A subtle pitfall is not explicitly checking for zeros. While the sorted string comparison inherently handles this, some alternative approaches might miss it:

Incorrect Approach:

def isFascinating(self, n: int) -> bool:
    s = str(n) + str(2 * n) + str(3 * n)
    if len(s) != 9:
        return False
    digit_count = [0] * 10
    for digit in s:
        digit_count[int(digit)] += 1
    # Forgot to check if digit_count[0] == 0!
    return all(digit_count[i] == 1 for i in range(1, 10))

Correct Fix: Add explicit zero check:

return digit_count[0] == 0 and all(digit_count[i] == 1 for i in range(1, 10))

The beauty of the sorted string approach is that it implicitly handles all these edge cases - if there's a zero, the sorted string would be "012345678" or similar, which won't match "123456789".