Check if The Number is Fascinating

EASY

Description

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

Checkout 3 different approaches to solve Check if The Number is Fascinating. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check if The Number is Fascinating. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Check if The Number is Fascinating

Patterns:

Math

Data Structures:

Hash Table