Scale Engineer

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.

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");    }}

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.

Solutions

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 ; } }

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 →

Next problem