LeetCode 2729 - Check if The Number is Fascinating

LeetCode Problem 2729

Difficulty: 🟢 Easy
Topics: Hash Table, Math

Solution

Problem Understanding

The problem gives us a three digit integer n. We must determine whether n is a fascinating number.

A number is considered fascinating when we concatenate three values together:

1. n
2. 2 * n
3. 3 * n

After concatenation, the resulting number must contain every digit from 1 through 9 exactly once. The digit 0 must not appear at all.

For example, if n = 192:

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

Concatenating them produces:

192384576

This string contains every digit from 1 to 9 exactly one time, so the answer is true.

The input constraints are very small:

100 <= n <= 999

Since the number always has exactly three digits, the concatenated result can contain at most nine digits. That means performance is not a concern here, and even straightforward solutions are efficient enough.

There are several important edge cases to keep in mind.

A result containing 0 must immediately fail. For example:

100 -> 100200300

The concatenated string contains multiple zeroes, so it is not fascinating.

Repeated digits also invalidate the number. Even if all digits from 1 to 9 appear, any duplication makes the answer false.

Another subtle case occurs when the concatenated string has fewer than nine digits. This means some digits are missing automatically, so the number cannot be fascinating.

Approaches

Brute Force Approach

The brute force method generates the concatenated number and checks whether every digit from 1 to 9 appears exactly once.

We can do this by:

1. Building the concatenated string.
2. Counting the frequency of every digit.
3. Verifying:

• no digit is 0
• every digit from 1 to 9 appears exactly once

This approach is correct because it directly checks the exact definition given in the problem statement.

Although it is called brute force, the input size is tiny. The concatenated string has at most nine characters, so the algorithm is effectively constant time.

Optimal Approach

The optimal approach uses a hash set.

Instead of storing counts for all digits, we observe that:

• the final result must contain exactly 9 digits
• every digit must be unique
• 0 cannot appear

So we can:

1. Build the concatenated string.
2. Check whether its length is exactly 9.
3. Insert digits into a set.
4. If we ever encounter 0 or a duplicate digit, return false.
5. Otherwise return true.

This works because a valid fascinating number must contain exactly the nine distinct digits 1 through 9.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Uses digit frequency counting
Optimal	O(1)	O(1)	Uses a hash set to detect duplicates quickly

Algorithm Walkthrough

1. Compute the three required numbers:

• n
• 2 * n
• 3 * n

2. Convert them to strings and concatenate them together.

This creates the exact sequence we must validate according to the problem statement. 3. Check whether the concatenated string has length 9.

A fascinating number must contain exactly the digits 1 through 9, so the total length must be exactly nine characters. 4. Create an empty hash set called seen_digits.

The set helps us efficiently detect duplicate digits. 5. Iterate through each character in the concatenated string.

For every digit:

• if the digit is '0', return false
• if the digit already exists in the set, return false
• otherwise insert it into the set

6. If the loop finishes successfully, return true.

At this point:

• no digit was 0
• no digit was duplicated
• length is exactly 9

Therefore the string must contain digits 1 through 9 exactly once.

Why it works

The algorithm checks all conditions required by the definition of a fascinating number.

Because the concatenated string has length 9, contains no zeroes, and contains no repeated digits, the only possible digits are exactly 1 through 9, each appearing once. Therefore the algorithm correctly determines whether the number is fascinating.

Python Solution

class Solution:
    def isFascinating(self, n: int) -> bool:
        concatenated = str(n) + str(2 * n) + str(3 * n)

        if len(concatenated) != 9:
            return False

        seen_digits = set()

        for digit in concatenated:
            if digit == '0' or digit in seen_digits:
                return False

            seen_digits.add(digit)

        return True

The implementation starts by constructing the concatenated string exactly as required by the problem.

The length check is performed early because a fascinating number must contain exactly nine digits. If the length is different, we can immediately return False.

A set named seen_digits stores digits we have already encountered. During iteration:

• encountering '0' immediately invalidates the number
• encountering a duplicate digit also invalidates the number

If the loop completes without returning False, then all digits are unique and nonzero, which guarantees the string contains digits 1 through 9 exactly once.

Go Solution

func isFascinating(n int) bool {
    concatenated := fmt.Sprintf("%d%d%d", n, 2*n, 3*n)

    if len(concatenated) != 9 {
        return false
    }

    seenDigits := make(map[rune]bool)

    for _, digit := range concatenated {
        if digit == '0' || seenDigits[digit] {
            return false
        }

        seenDigits[digit] = true
    }

    return true
}

The Go implementation follows the same logic as the Python solution.

A map[rune]bool is used instead of a Python set. Each digit is checked for duplication and for the forbidden value '0'.

Go requires explicit string formatting, so fmt.Sprintf is used to build the concatenated string.

Worked Examples

Example 1

Input: n = 192

First compute the multiples:

Expression	Value
n	192
2 * n	384
3 * n	576

Concatenated string:

192384576

Now iterate through the digits.

Current Digit	Seen Set Before	Action	Seen Set After
1	{}	add	{1}
9	{1}	add	{1,9}
2	{1,9}	add	{1,9,2}
3	{1,9,2}	add	{1,9,2,3}
8	{1,9,2,3}	add	{1,9,2,3,8}
4	{1,9,2,3,8}	add	{1,9,2,3,8,4}
5	{1,9,2,3,8,4}	add	{1,9,2,3,8,4,5}
7	{1,9,2,3,8,4,5}	add	{1,9,2,3,8,4,5,7}
6	{1,9,2,3,8,4,5,7}	add	{1,9,2,3,8,4,5,7,6}

No duplicates and no zeroes were found, so the answer is:

true

Example 2

Input: n = 100

Compute the multiples:

Expression	Value
n	100
2 * n	200
3 * n	300

Concatenated string:

100200300

Iteration begins:

Current Digit	Result
1	valid
0	invalid, return false

The digit 0 appears, so the number is not fascinating.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The concatenated string has at most 9 digits
Space	O(1)	The set stores at most 9 digits

Even though we iterate through the digits, the total number of characters is bounded by a constant. Therefore both time and space usage are constant.

Test Cases

solution = Solution()

assert solution.isFascinating(192) == True      # Provided valid example
assert solution.isFascinating(100) == False     # Contains zeroes
assert solution.isFascinating(783) == True      # Another known fascinating number
assert solution.isFascinating(267) == False     # Repeated digits
assert solution.isFascinating(879) == False     # Duplicate digits appear
assert solution.isFascinating(327) == True      # Valid fascinating number
assert solution.isFascinating(123) == False     # Missing digits
assert solution.isFascinating(999) == False     # Heavy duplication
assert solution.isFascinating(101) == False     # Zero appears immediately
assert solution.isFascinating(219) == True      # Valid fascinating number

Test	Why
192	Official positive example
100	Official negative example with zeroes
783	Valid fascinating number
267	Tests duplicate digits
879	Tests repeated digits across products
327	Another valid fascinating number
123	Missing required digits
999	Extreme duplication case
101	Zero handling
219	Confirms additional valid case

Edge Cases

One important edge case is when the concatenated string contains zeroes. This is easy to overlook because the digits may otherwise appear unique. For example, 100 generates 100200300. The implementation explicitly checks for '0' during iteration and immediately returns False.

Another important case is duplicate digits appearing across different multiples. A number may look promising at first, but repeated digits invalidate it. For example, 267 produces repeated digits in the concatenated result. The hash set guarantees duplicates are detected efficiently and correctly.

A third edge case occurs when the concatenated result does not contain exactly nine digits. Some numbers generate shorter results, meaning at least one digit from 1 through 9 is missing automatically. The implementation handles this with an early length check before processing digits.