algoadvance

Leetcode 2729. Check if The Number is Fascinating

Problem Statement

The problem is taken from LeetCode, and it is stated as follows:

A number n is considered fascinating if, after multiplying it by 1, 2, and 3, and then concatenating the results in the order they were obtained, the resulting number contains all the digits from 1 to 9 exactly once.

Given an integer n, your task is to determine if n is a fascinating number. Return true if n is fascinating, otherwise return false.

Example:

Input: n = 192
Output: true
Explanation: We get three fragments: 192, 384, 576 and after concatenating them, we get the number 192384576 which contains all digits from 1 to 9 exactly once.

Clarifying Questions

  1. Input Range: Are there constraints on the value of n (e.g., positive integers only)?
    • Typically, n is assumed to be a positive integer within a reasonable range for usual integer operations.
  2. Data Type: Should n be within the range of int type in C++?
    • Yes, we will assume n is within the range of a standard int.

Strategy

  1. Multiplication and Concatenation:
    • Multiply n by 1, 2, and 3 to get three numbers.
    • Convert those numbers to strings and concatenate them.
  2. Validation:
    • Ensure the concatenated string has exactly 9 digits.
    • Check that each digit from ‘1’ to ‘9’ appears exactly once in the concatenated string.
  3. Edge Cases:
    • If n leads to a concatenated string longer or shorter than 9 digits, it cannot be fascinating.
    • Handle cases where n is particularly small or large but still within the range of typical integer operations.

Code

#include <iostream>
#include <unordered_set>
#include <string>

bool isFascinating(int n) {
    // Concatenate the numbers n, 2n, and 3n as strings
    std::string concatenated = std::to_string(n) + std::to_string(2 * n) + std::to_string(3 * n);
    
    // Check if the concatenated string has exactly 9 digits
    if (concatenated.size() != 9) {
        return false;
    }
    
    // Use a set to check for unique digits from 1 to 9
    std::unordered_set<char> digits;
    for (char c : concatenated) {
        // Check if it is a digit between '1' and '9'
        if (c < '1' || c > '9') {
            return false;
        }
        digits.insert(c);
    }
    
    // Check if the set contains exactly 9 unique digits
    return digits.size() == 9;
}

int main() {
    int test_num = 192; // example number
    if (isFascinating(test_num)) {
        std::cout << test_num << " is a fascinating number.\n";
    } else {
        std::cout << test_num << " is not a fascinating number.\n";
    }
    return 0;
}

Time Complexity

Hence, the overall time complexity is O(1), making this solution efficient and scalable for the given problem constraints.

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