algoadvance

Leetcode 2729. Check if The Number is Fascinating

Problem Statement

2729. Check if The Number is Fascinating

You are given an integer n and a fascinating number is a number such that when it is multiplied by 1, 2, and 3, and the results are concatenated together in order, all the digits from 1 to 9 are present exactly once.

For example:

• 192 is a fascinating number because 192 * 1 = 192, 192 * 2 = 384, and 192 * 3 = 576, and 192384576 contains all the digits from 1 to 9 exactly once.
• 100 is not a fascinating number as the concatenation 100200300 contains multiple zeros and doesn’t contain some other digits.

Given an integer n, return true if it is a fascinating number, or false otherwise.

Clarifying Questions

1. Range of n: Are there any constraints on the value of n?
   • Assumption: Typically, such problems would have a range constraint like 1 <= n <= 10^4 but this needs to be confirmed.
2. Negative numbers: Are negative numbers considered in this problem?
   • Assumption: Typically, fascinating numbers would be positive integers.
3. Return type: Should we return true/false as a boolean?
   • Assumption: Yes, the output is expected to be a boolean.

Strategy

1. Generate and Concatenate: Calculate n * 1, n * 2, and n * 3. Concatenate these results into a single string.

2. Verify Digits: Ensure that the concatenated string contains exactly nine distinct digits without any repetition, and that these digits are exactly 1 through 9.

3. Immediate Validation: If the length of the concatenated string is not 9, return false immediately as it cannot be valid.

Time Complexity

• The solution involves basic arithmetic operations and string manipulations which are constant time (O(1) for multiplication and constant-time for string concatenations due to fixed lengths).
• Checking the string for the exact digits and uniqueness involves linear scans through a fixed-length string.

Hence, the overall time complexity is O(1), as the operations work on fixed-size data.

Implementation

public class Solution {
    public boolean isFascinating(int n) {
        // Generate the concatenated string
        String concatenated = "" + n + (n * 2) + (n * 3);
        
        // If the length of concatenated string is not 9, it's not fascinating
        if (concatenated.length() != 9) {
            return false;
        }
        
        // We need every digit from 1 to 9 to appear exactly once
        boolean[] digits = new boolean[10];
        
        for (char ch : concatenated.toCharArray()) {
            int digit = ch - '0';
            // If the digit is 0 or already seen, return false
            if(digit == 0 || digits[digit]) {
                return false;
            }
            digits[digit] = true;
        }
        
        // Ensure all digits from 1 to 9 are seen exactly once
        for (int i = 1; i <= 9; i++) {
            if (!digits[i]) {
                return false;
            }
        }
        return true;
    }
}

You can use this code to determine if a given number n is a fascinating number by calling isFascinating(n) with the desired integer value. The solution ensures precise verification in constant time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?