Skip to main content

Fascinating Number Problem (Geeks for Geeks)

This tutorial contains a complete walk-through of the Fascinating Number problem from the Geeks for Geeks website. It features the implementation of the solution code in two programming languages: Python and C++.

Problem Description​

Given a number N. Your task is to check whether it is fascinating or not.

Fascinating Number: When a number(should contain 3 digits or more) is multiplied by 2 and 3, and when both these products are concatenated with the original number, then it results in all digits from 1 to 9 present exactly once.

Examples​

Example 1:

Input: N = 192
Output: Fascinating
Explanation: After multiplication with 2 and 3, and concatenating with original number, number will become 192384576 which contains all digits from 1 to 9.

Example 2:

Input: N = 853
Output: Not Fascinating
Explanation: It's not a fascinating number.

Your Task​

You don't need to read input or print anything. Your task is to complete the function fascinating() which takes the integer n parameters and returns boolean (True or False) denoting the answer.

Expected Time Complexity: O(1)O(1) Expected Auxiliary Space: O(1)O(1)

Constraints​

100 <= N <= 2*10^9

Problem Explanation​

The problem is to determine if a given number N is a fascinating number. A fascinating number is defined as follows:

  1. The number must have at least three digits.
  2. Multiply the number by 2 and 3 to get two products.
  3. Concatenate the original number, the product of the number and 2, and the product of the number and 3 into a single string.
  4. The concatenated string should contain all digits from 1 to 9 exactly once, with no other digits present (e.g., no zeros).

Code Implementation​

Written by @iamanolive
class Solution:

def fascinating(self, n):
m2 = n * 2
m3 = n * 3
num = str(n) + str(m2) + str(m3)
num = "".join(sorted(num))
zero_count = num.count("0")
if (num.find("123456789") == -1):
return False
elif (len(num) - zero_count > 9):
return False
else:
return True

Example Walkthrough​

For N = 192:

  1. Original number: 192
  2. Multiply by 2: 192 × 2 = 384
  3. Multiply by 3: 192 × 3 = 576
  4. Concatenate: "192" + "384" + "576" = "192384576"
  5. Check if the concatenated string contains all digits from 1 to 9 exactly once: "192384576" contains each digit from 1 to 9 exactly once.

Therefore, 192 is a fascinating number.

Solution Logic:​

  1. Compute the Products: Multiply the number N by 2 and 3 to get two new numbers.
  2. Concatenate the Results: Convert the original number and the two products to strings and concatenate them.
  3. Sort and Check Digits: Sort the concatenated string and check if it contains the sequence "123456789" exactly once.
  4. Verify Length: Ensure there are no extra digits (like zero or repetitions). The total length of digits should be exactly 9, excluding any zeros.

Time Complexity​

The time complexity is O(1)O(1) because the operations involve a fixed number of steps regardless of the size of N:

  • Multiplication and string concatenation are constant time operations.
  • Sorting a string of fixed length (at most 9 characters) is a constant time operation.
  • Checking for the sequence "123456789" in a fixed-length string is also a constant time operation.

Space Complexity​

The space complexity is O(1)O(1) as well since the operations use a constant amount of extra space for storing the products and concatenated strings.

References​