# Check if The Number is Fascinating
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-the-number-is-fascinating)
Canonical: https://scaleengineer.com/dsa/problems/check-if-the-number-is-fascinating
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table
---
## Problem
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
## String Concatenation and Sorting
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public boolean isFascinating(int n) {
        String s = "" + n + (2 * n) + (3 * n);
        if (s.length() != 9) {
            return false;
        }
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String sortedStr = new String(chars);
        return sortedStr.equals("123456789");
    }
}
```
### 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`.

## String Concatenation and Frequency Counting
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public boolean isFascinating(int n) {
        String s = "" + n + (2 * n) + (3 * n);
        if (s.length() != 9) {
            return false;
        }
        boolean[] seen = new boolean[10];
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit == 0 || seen[digit]) {
                return false;
            }
            seen[digit] = true;
        }
        return true;
    }
}
```
### 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`.

## Optimized Mathematical Digit Manipulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public boolean isFascinating(int n) {
        // Optimization: If n > 333, the concatenated number will have > 9 digits.
        if (n > 333) {
            return false;
        }
        
        boolean[] seen = new boolean[10];
        
        // Check digits for n
        if (!checkAndUpdate(n, seen)) return false;
        // Check digits for 2*n
        if (!checkAndUpdate(n * 2, seen)) return false;
        // Check digits for 3*n
        if (!checkAndUpdate(n * 3, seen)) return false;
        
        return true;
    }

    private boolean checkAndUpdate(int num, boolean[] seen) {
        int temp = num;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0 || seen[digit]) {
                return false; // Found a zero or a duplicate
            }
            seen[digit] = true;
            temp /= 10;
        }
        return true;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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" ; } };
```

### Python

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