Leetcode 2729: Check if The Number is Fascinating
You are given a three-digit integer n. We define a number as fascinating if, when you concatenate n, 2 * n, and 3 * n, the resulting number contains all digits from 1 to 9 exactly once and does not contain any zeros.
Problem
Approach
Steps
Complexity
Input: A three-digit integer n.
Example: n = 192
Constraints:
• 100 <= n <= 999
Output: Return true if the number is fascinating, otherwise return false.
Example: true
Constraints:
• The result will be a boolean value.
Goal: Determine if the concatenated number contains all digits from 1 to 9 exactly once without zeros.
Steps:
• Concatenate n, 2 * n, and 3 * n into a single string.
• Check if the string contains exactly the digits 1 to 9 with no repetitions or zeros.
Goal: The constraints ensure that n is a valid 3-digit number.
Steps:
• 100 <= n <= 999
Assumptions:
• n is always a valid three-digit number.
• Input: Example 1
• Explanation: For n = 192, concatenating 192, 384, and 576 gives 192384576, which contains all digits from 1 to 9 exactly once.
• Input: Example 2
• Explanation: For n = 100, concatenating 100, 200, and 300 gives 100200300, which contains zeros and doesn't satisfy the conditions.
Approach: The approach is to check if the concatenated number contains all the digits from 1 to 9 exactly once without any zeros.
Observations:
• The concatenated result must contain exactly the digits 1 through 9.
• We need to check if the concatenated string has the correct digits and no zeros.
Steps:
• Multiply n by 2 and 3.
• Concatenate n, 2 * n, and 3 * n into a string.
• Check if the resulting string has exactly 9 digits and contains only digits from 1 to 9 with no zeros.
Empty Inputs:
• There are no empty inputs since n is always a three-digit number.
Large Inputs:
• n is always between 100 and 999, so no large inputs to consider.
Special Values:
• Check for numbers like 100 or multiples that result in zeros in the concatenation.
Constraints:
• n must be a valid three-digit number.
bool isFascinating(int n) {
int n1 = 2 * n;
int n2 = 3 * n;
vector<bool> yes(10, false);
string s = to_string(n) + to_string(n1) + to_string(n2);
for(int i = 0; i < s.size(); i++) {
if(s[i] == '0') return false;
if(yes[s[i] - '0']) return false;
yes[s[i] - '0'] = true;
}
return true;
}
1 : Function Definition
bool isFascinating(int n) {
The function `isFascinating` is defined, taking an integer `n` and returning a boolean indicating whether `n` is a fascinating number.
2 : Variable Initialization
int n1 = 2 * n;
The variable `n1` is initialized to `2 * n`, which is used to create the concatenated string for further checks.
3 : Variable Initialization
int n2 = 3 * n;
The variable `n2` is initialized to `3 * n`, representing the third part of the concatenated string.
4 : Array Initialization
vector<bool> yes(10, false);
A vector `yes` is initialized with 10 elements, all set to `false`. This will be used to track whether a digit from 1 to 9 has already appeared in the concatenated string.
5 : String Concatenation
string s = to_string(n) + to_string(n1) + to_string(n2);
The integers `n`, `n1`, and `n2` are converted to strings and concatenated together to form the string `s`.
6 : Loop Start
for(int i = 0; i < s.size(); i++) {
A loop is initiated to iterate over each character of the concatenated string `s`.
7 : Zero Check
if(s[i] == '0') return false;
If any character in the string is '0', the function returns `false`, as a fascinating number cannot contain the digit '0'.
8 : Repetition Check
if(yes[s[i] - '0']) return false;
If the digit has already appeared in the string (tracked by the `yes` array), the function returns `false`, ensuring all digits are unique.
9 : Mark Digit as Seen
yes[s[i] - '0'] = true;
The corresponding index in the `yes` vector is set to `true` to mark that digit as seen.
10 : Return True
return true;
If the loop completes without returning `false`, the function returns `true`, indicating that the number `n` is a fascinating number.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant since the operations do not depend on the size of the input beyond simple arithmetic and string checks.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only store a few integer variables and a string of fixed length.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus