Check if The Number is Fascinating

Easy

#2455Time: O(1). The operations are performed on numbers and strings of a small, constant size. String concatenation, converting to a char array (`O(L)`), sorting (`O(L log L)`), and string comparison (`O(L)`) all take constant time because the length `L` is fixed at 9 for any valid candidate.Space: O(1). While we create a string and a character array, their maximum size is determined by the concatenation, which for a fascinating number must be 9. Since the size is constant and does not scale with the input `n`'s magnitude, the space complexity is constant.

Patterns

Math

Data structures

Hash Table

Prompt

You are given an integer n that consists of exactly 3 digits.

We call the number n fascinating if, after the following modification, the resulting number contains all the digits from 1 to 9 exactly once and does not contain any 0's:

Concatenate n with the numbers 2 * n and 3 * n.

Return true if n is fascinating, or false otherwise.

Concatenating two numbers means joining them together. For example, the concatenation of 121 and 371 is 121371.

Example 1:

Input: n = 192
Output: true
Explanation: We concatenate the numbers n = 192 and 2 * n = 384 and 3 * n = 576. The resulting number is 192384576. This number contains all the digits from 1 to 9 exactly once.

Example 2:

Input: n = 100
Output: false
Explanation: We concatenate the numbers n = 100 and 2 * n = 200 and 3 * n = 300. The resulting number is 100200300. This number does not satisfy any of the conditions.

Constraints:

100 <= n <= 999

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves creating the concatenated number as a string and then verifying its properties. The central idea is that if a 9-digit number contains every digit from 1 to 9 exactly once, then its characters, when sorted, must form the string "123456789". This provides a simple way to check the condition.

Algorithm

Calculate n2 = 2 * n and n3 = 3 * n.
Convert n, n2, and n3 to strings and concatenate them to form a single string s.
Check if the length of s is exactly 9. If not, the number cannot be fascinating, so return false.
Convert the string s into a character array.
Sort the character array in ascending order.
Create a new string from the sorted character array.
Compare this sorted string with the target string "123456789". If they are identical, it means the original concatenated number contained all digits from 1 to 9 exactly once. Return true. Otherwise, return false.

Walkthrough

The first step is to perform the required calculation and concatenation. We compute 2 * n and 3 * n and then join n, 2 * n, and 3 * n together into a single string. A crucial preliminary check is the length of this string. For a number to be a permutation of digits 1 through 9, it must have exactly 9 digits. If the length is not 9, we can immediately conclude it's not fascinating. If the length is correct, we proceed by converting the string to a character array, which allows us to use standard sorting algorithms. After sorting the array, we convert it back to a string. The final step is a direct comparison of this sorted string with the constant string "123456789". An exact match confirms that the number is fascinating.

1import java.util.Arrays;2 3class Solution {4    public boolean isFascinating(int n) {5        String s = "" + n + (2 * n) + (3 * n);6        if (s.length() != 9) {7            return false;8        }9        char[] chars = s.toCharArray();10        Arrays.sort(chars);11        String sortedStr = new String(chars);12        return sortedStr.equals("123456789");13    }14}

Complexity

Time

O(1). The operations are performed on numbers and strings of a small, constant size. String concatenation, converting to a char array (`O(L)`), sorting (`O(L log L)`), and string comparison (`O(L)`) all take constant time because the length `L` is fixed at 9 for any valid candidate.

Space

O(1). While we create a string and a character array, their maximum size is determined by the concatenation, which for a fascinating number must be 9. Since the size is constant and does not scale with the input `n`'s magnitude, the space complexity is constant.

Trade-offs

Pros

The logic is straightforward and easy to understand.
It leverages built-in functions for sorting and string comparison, leading to concise code.

Cons

Involves multiple steps: string conversion, concatenation, array conversion, sorting, and new string creation, which can be less performant than direct counting methods.
The core logic relies on sorting, which has a time complexity of O(L log L), making it algorithmically less efficient than linear O(L) approaches, even though L is a small constant in this specific problem.

This method also starts by creating the concatenated string but uses a more direct and efficient way to check the digit properties. Instead of sorting, it employs a frequency map (or a simple boolean array) to ensure that the string contains no zeros and no repeated digits. Given the initial check that the string length is 9, these two conditions are sufficient to prove the number is fascinating.

Algorithm

Calculate n2 = 2 * n and n3 = 3 * n.
Concatenate n, n2, and n3 into a single string s.
If the length of s is not 9, return false.
Create a frequency counter, such as a boolean array seen of size 10, initialized to false.
Iterate through each character of the string s.
For each character, convert it to its integer digit value d.
Check two conditions:
- If d is 0, return false.
- If seen[d] is already true, it's a duplicate digit. Return false.
If the checks pass, mark the digit as seen by setting seen[d] = true.
If the loop finishes without returning false, it means the string contained 9 unique non-zero digits. Return true.

Walkthrough

Similar to the previous approach, we first form the concatenated string from n, 2*n, and 3*n. We check if its length is 9; if not, we return false. Then, we initialize a boolean array seen of size 10 to keep track of which digits (0-9) we have encountered. We iterate through the characters of the concatenated string one by one. For each character, we get its integer value. We immediately return false if the digit is 0 or if our seen array indicates we have already encountered this digit. If it's a new, non-zero digit, we record it by setting the corresponding index in seen to true. If we successfully iterate through all 9 characters without any issues, it confirms that all digits are unique and non-zero, so the number is fascinating.

1class Solution {2    public boolean isFascinating(int n) {3        String s = "" + n + (2 * n) + (3 * n);4        if (s.length() != 9) {5            return false;6        }7        boolean[] seen = new boolean[10];8        for (char c : s.toCharArray()) {9            int digit = c - '0';10            if (digit == 0 || seen[digit]) {11                return false;12            }13            seen[digit] = true;14        }15        return true;16    }17}

Complexity

Time

O(1). The time complexity is dominated by iterating through the 9 characters of the string. This is a constant number of operations, making the overall time complexity constant. It's generally faster than the sorting approach due to better constant factors.

Space

O(1). The space for the concatenated string (length 9) and the boolean array (size 10) is constant.

Trade-offs

Pros

Algorithmically more efficient than sorting, with a linear time complexity relative to the string length.
Directly checks the problem's conditions (no zeros, no duplicates) in a single pass.

Cons

Still relies on the overhead of creating string objects and concatenating them.

This is the most efficient approach as it avoids string conversions and allocations entirely, working directly with integer arithmetic. It incorporates a powerful optimization based on the problem's constraints. By realizing that the concatenated number must have exactly 9 digits, we can deduce that n must be in the range [100, 333]. This allows us to immediately reject a large portion of the input range, making the solution extremely fast.

Algorithm

Optimization: A number n can only be fascinating if the concatenated number n, 2*n, 3*n has exactly 9 digits. This only occurs for 100 <= n <= 333. If n > 333, the concatenated number will have 10 or more digits. So, if n > 333, return false immediately.
Create a boolean array seen of size 10, initialized to false.
Create a helper process to check the digits of an integer.
For a given number, iterate through its digits using modulo (% 10) and integer division (/ 10).
For each digit, check if it's 0 or if seen[digit] is true. If so, return false from the main function.
Otherwise, set seen[digit] = true.
Apply this process sequentially for n, 2 * n, and 3 * n.
If all three numbers are processed without returning false, return true.

Walkthrough

The key insight is that the total number of digits in the concatenation of n, 2*n, and 3*n must be 9. Since n is a 3-digit number, this condition holds only if 2*n and 3*n are also 3-digit numbers. This is true only up to n=333. For n=334, 3*n=1002 which is a 4-digit number, making the total length 10. Therefore, we can add a check: if (n > 333) return false;.

For the remaining candidates, we use a boolean array seen to track digits. We define a routine that takes an integer, extracts its digits one by one using the num % 10 and num /= 10 pattern, and checks them against the seen array. If a digit is 0 or has been seen before, we know the number isn't fascinating. We apply this routine to n, then 2*n, and finally 3*n. If all digits from all three numbers are processed successfully, the number is fascinating.

1class Solution {2    public boolean isFascinating(int n) {3        // Optimization: If n > 333, the concatenated number will have > 9 digits.4        if (n > 333) {5            return false;6        }7        8        boolean[] seen = new boolean[10];9        10        // Check digits for n11        if (!checkAndUpdate(n, seen)) return false;12        // Check digits for 2*n13        if (!checkAndUpdate(n * 2, seen)) return false;14        // Check digits for 3*n15        if (!checkAndUpdate(n * 3, seen)) return false;16        17        return true;18    }19 20    private boolean checkAndUpdate(int num, boolean[] seen) {21        int temp = num;22        while (temp > 0) {23            int digit = temp % 10;24            if (digit == 0 || seen[digit]) {25                return false; // Found a zero or a duplicate26            }27            seen[digit] = true;28            temp /= 10;29        }30        return true;31    }32}

Complexity

Time

O(1). The number of arithmetic operations and loop iterations is small and constant. The early exit for `n > 333` makes it exceptionally fast for most of the input range.

Space

O(1). The only extra space used is a boolean array of fixed size 10.

Trade-offs

Pros

Highest performance due to avoiding string manipulation overhead.
Includes a powerful optimization that prunes the search space significantly.
Minimal memory usage.

Cons

The logic, while efficient, can be slightly more complex to implement compared to string-based solutions, especially for those less familiar with manual digit extraction.

Solutions

Solution

1class Solution { public boolean isFascinating ( int n ) { String s = "" + n + ( 2 * n ) + ( 3 * n ); int [] cnt = new int [ 10 ]; for ( char c : s . toCharArray ()) { if (++ cnt [ c - '0' ] > 1 ) { return false ; } } return cnt [ 0 ] == 0 && s . length () == 9 ; } }

1class Solution { public: bool isFascinating ( int n ) { string s = to_string ( n ) + to_string ( n * 2 ) + to_string ( n * 3 ); sort ( s . begin (), s . end ()); return s == "123456789" ; } };

1class Solution : def isFascinating ( self , n : int ) -> bool : s = str ( n ) + str ( 2 * n ) + str ( 3 * n ) return "" . join ( sorted ( s )) == "123456789"

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public boolean isFascinating ( int n ) { String s = "" + n + ( 2 * n ) + ( 3 * n ); int [] cnt = new int [ 10 ]; for ( char c : s . toCharArray ()) { if (++ cnt [ c - '0' ] > 1 ) { return false ; } } return cnt [ 0 ] == 0 && s . length () == 9 ; } }

1class Solution { public: bool isFascinating ( int n ) { string s = to_string ( n ) + to_string ( n * 2 ) + to_string ( n * 3 ); sort ( s . begin (), s . end ()); return s == "123456789" ; } };

1class Solution : def isFascinating ( self , n : int ) -> bool : s = str ( n ) + str ( 2 * n ) + str ( 3 * n ) return "" . join ( sorted ( s )) == "123456789"

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.