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:
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 <= 999Problem Overview: A number is called fascinating if the concatenation of n, 2 * n, and 3 * n forms a 9-digit string containing each digit from 1 to 9 exactly once. Any repetition, missing digit, or the presence of 0 means the number is not fascinating.
Approach 1: Set-Based Unique Digit Verification (Time: O(d), Space: O(d))
Compute 2 * n and 3 * n, then concatenate them with n to form a single string. Iterate through the characters and insert each digit into a set. If the string length is not 9, or the set contains 0, or the final set size is not 9, the number fails the fascinating condition. The set guarantees uniqueness while iteration verifies all digits are valid. This approach relies on constant‑size digit processing, making the complexity effectively O(1) since d ≤ 9.
This method uses concepts similar to a hash lookup, where insertion and membership checks happen in constant time. If you want to review the underlying structure, see hash table fundamentals.
Approach 2: Direct Character Comparison (Time: O(d), Space: O(1))
Instead of storing digits in a set, concatenate n, 2n, and 3n into a string and count digit frequencies using a fixed array of size 10. Iterate through the string and increment the counter for each digit. The number is fascinating only if digits 1 through 9 each appear exactly once and digit 0 never appears. This avoids dynamic structures and relies purely on index access.
This technique works well because the problem is driven by digit manipulation and simple arithmetic operations. If you want to explore more problems based on number properties, review math techniques commonly used in interview questions.
Recommended for interviews: The set-based approach is usually the first solution developers write because it clearly expresses the “unique digits” requirement. The frequency-array version is slightly more optimized and avoids extra structures. Showing the set approach first demonstrates clear reasoning, while the direct counting method shows attention to constant-space optimization.
This approach uses a set to verify the uniqueness of digits. After concatenating n, 2*n, and 3*n, we convert the result into a set of characters. The number is considered fascinating if the set contains exactly the digits '1' to '9', and if its length is 9.
We use sprintf to concatenate n, 2*n, and 3*n into a string. We then count the frequency of each digit using an array. If the digit '0' appears or any digit appears more than once, we return false. Otherwise, we verify if all digits from 1 to 9 appear exactly once.
Time Complexity: O(1) because the number of digits is constant.
Space Complexity: O(1) because only a fixed amount of extra space is needed.
This approach constructs the concatenated string from n, 2*n, and 3*n and directly checks if the resulting string matches the sorted version of '123456789'. Since the order must not affect the presence of digits between 1 to 9, sorting provides a straightforward comparison for validation.
In this C solution, the concatenated result of n, 2*n, and 3*n is stored in a character array. We use qsort to sort the characters and then check if the resultant sorted string is "123456789". This determines the number's fascinating status.
Time Complexity: O(1), due to constant and fixed string size.
Space Complexity: O(1), since we're using predefined character buffers.
| Approach | Complexity |
|---|---|
| Set-Based Unique Digit Verification | Time Complexity: O(1) because the number of digits is constant. |
| Direct Character Comparison | Time Complexity: O(1), due to constant and fixed string size. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set-Based Unique Digit Verification | O(d) | O(d) | Best for readability and quick implementation when checking digit uniqueness. |
| Direct Character Comparison (Frequency Array) | O(d) | O(1) | Useful when minimizing memory usage or avoiding hash-based structures. |
Check if The Number is Fascinating || Biweekly Contest 106 solution with Explanation • Learn to Code • 316 views views
Watch 8 more video solutions →Practice Check if The Number is Fascinating with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor