1056. Confusing Number
Problem Description
A confusing number is defined as an integer which, when rotated by 180 degrees, yields a different number, but still maintains its validity by only consisting of valid digits. Each digit has its rotated counterpart as follows:
0
,1
,8
remain unchanged when rotated (0
->0
,1
->1
,8
->8
).6
and9
are swapped when rotated (6
->9
,9
->6
).- Digits
2
,3
,4
,5
, and7
do not have valid rotations and thus make a number invalid if present after rotation.
When a number is rotated, we disregard leading zeros. For example, 8000
becomes 0008
after rotation, which we treat as 8
.
The task is to determine whether a given integer n
is a confusing number. If n
is a confusing number, the function should return true
; otherwise, it returns false
.
Intuition
To solve this problem, we need to check two things:
- Whether each digit in the given number has a valid rotation.
- Whether the rotated number is different from the original number.
To start with, we map each digit to its rotated counterpart (if any), with invalid digits being mapped to -1
. This gives us the array d
with precomputed rotated values for all possible single digits:
[0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
The intuition for the solution is to iterate through the digits of n
from right to left, checking that each digit has a valid rotated counterpart, and simultaneously building the rotated number. This is achieved by the following steps:
- Initialize two variables,
x
andy
.x
will hold the original number which we'll deconstruct digit by digit, andy
will be used to construct the rotated number. - We use a loop to process each digit of
x
until all digits have been processed:x, v = divmod(x, 10)
uses Python'sdivmod
function to get the last digitv
and updatex
to remove this last digit.- We then check if the current digit
v
has a valid rotation by looking it up in the arrayd
. Ifd[v]
is-1
, we have an invalid digit; in this case, we returnfalse
. - If
v
is valid, we compute the new rotated digit and add it toy
by shiftingy
to the left (by a factor of 10) and then addingd[v]
.
- After processing all digits of
x
, we end up withy
, which is the number formed after rotatingn
. We comparey
withn
to check if they are different. If they are the same, it means the number is not confusing and we returnfalse
. Otherwise, we returntrue
.
Learn more about Math patterns.
Solution Approach
The implementation uses a simple algorithm that involves iterating through the digits of the given number to check for validity after rotation and building the rotated number at the same time.
Here's the breakdown:
-
Initialize variables: The solution starts with initializing two variables,
x
andy
.x
is assigned the value of the given numbern
and will be used to iterate through its digits.y
is initialized to 0 and will be used to construct the rotated number. -
Predefined rotations: A list
d
is created that defines the rotation of each digit. This list serves as a direct mapping, where the index represents the original digit and the value at that index represents the rotated digit. If a digit is invalid when rotated (e.g.,2
,3
,4
,5
, or7
), its rotated value in the list is-1
. -
Iterate through digits: The while-loop is used to iterate through the digits of
n
from right to left. Inside the loop,divmod(x, 10)
obtains the rightmost digitv
ofx
and updatesx
to eliminate the rightmost digit.divmod
is a Python built-in function that simultaneously performs integer division and modulo operation. -
Validity check: The solution then checks for the validity of each digit by referencing the
d
list. Ifd[v]
is-1
, it means the digitv
is invalid upon rotation, and the function returnsfalse
. An example is if the original number contains a2
, since2
does not have a valid rotation equivalent. -
Building rotated number: If the digit is valid, the rotated digit (found at
d[v]
) is added toy
. To maintain the correct place value,y
is first multiplied by 10 and then the rotated digit is added to it. -
Final check: After processing the entire number,
y
would now be the rotated number. The rotated numbery
is then compared with the original numbern
. If they are identical, it means that the rotation has not changed the number, hence it is not a confusing number and the function returnsfalse
. Otherwise, it returnstrue
.
This algorithm efficiently checks each digit of the number without the need for additional data structures and effectively builds the rotated number in-place using basic arithmetic operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the number 619
as a small example to illustrate the solution approach.
-
Initialize variables:
x
is assigned the value ofn
, sox
becomes619
.y
is initialized to0
.
-
Predefined rotations:
- We use the list
d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
.
- We use the list
-
Iterate through digits:
619
has three digits, so we will perform the process below three times, once for each digit.
-
Validity check and building rotated number:
- First Iteration (rightmost digit
9
):x, v = divmod(619, 10)
givesx = 61
,v = 9
.d[v] = d[9]
is6
(valid rotation), so we move to buildingy
.y = y * 10 + d[v] = 0 * 10 + 6 = 6
.
- Second Iteration (middle digit
1
):x, v = divmod(61, 10)
givesx = 6
,v = 1
.d[v] = d[1]
is1
,1
remains the same after rotation.y = y * 10 + d[v] = 6 * 10 + 1 = 61
.
- Third Iteration (leftmost digit
6
):x, v = divmod(6, 10)
givesx = 0, v = 6
(asx
is now less than10
).d[v] = d[6]
is9
(valid rotation).y = y * 10 + d[v] = 61 * 10 + 9 = 619
.
- First Iteration (rightmost digit
-
Final check:
- Now
x
is0
, and we have finished processing the digits. We havey = 619
. - We compare
y
with the originaln
, and in this case,619
is equal to619
, meaning the number did not change upon rotation. - Since the rotated number is identical to the original number,
619
is not a confusing number according to our definition.
- Now
Therefore, the function would return false
for 619
because rotating the number gives us the same number instead of a different number.
To see how a confusing number would work with this example, let's rotate the number 68
:
- Initialize
x = 68
andy = 0
. x, v = divmod(68, 10)
givesx = 6
,v = 8
.d[8]
is8
, soy = 0 * 10 + 8 = 8
.
x, v = divmod(6, 10)
givesx = 0
,v = 6
.d[6]
is9
, soy = 8 * 10 + 9 = 89
.
- The original number
68
is different from the rotated number89
, therefore the function would returntrue
, indicating that68
is indeed a confusing number.
Solution Implementation
1class Solution:
2 def confusingNumber(self, n: int) -> bool:
3 """
4 Determine if the given number is a confusing number. A confusing number is a number that,
5 when rotated 180 degrees, becomes a different valid number. If any digit cannot be rotated,
6 or the number remains the same after rotation, it is not a confusing number.
7
8 :param n: The input number to be tested.
9 :return: True if n is a confusing number, False otherwise.
10 """
11
12 # Original number and transformed/rotated number
13 original_number = n
14 rotated_number = 0
15
16 # Mapping of digits after 180-degree rotation
17 rotation_map = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
18
19 # Process each digit of the original number
20 while original_number:
21 # Obtain the last digit and reduce the original number by one digit
22 original_number, last_digit = divmod(original_number, 10)
23
24 # Check for valid rotation, return False if rotation is invalid (indicated by -1)
25 if rotation_map[last_digit] < 0:
26 return False
27
28 # Build the rotated number by appending the rotated digit
29 rotated_number = rotated_number * 10 + rotation_map[last_digit]
30
31 # A number is confusing if it is different from its rotation
32 return rotated_number != n
33
1class Solution {
2 // Method to determine if a number is a confusing number
3 public boolean confusingNumber(int n) {
4 // Mappings from original digit to its possible flipped digit
5 // -1 indicates an invalid digit that doesn't have a valid transformation
6 int[] digitTransformations = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
7
8 // Original number
9 int originalNumber = n;
10 // Transformed number after flipping the digits
11 int transformedNumber = 0;
12
13 // Process each digit of the original number
14 while (originalNumber > 0) {
15 // Get the last digit of the current number
16 int digit = originalNumber % 10;
17 // Check if the digit has a valid transformation
18 if (digitTransformations[digit] < 0) {
19 // If not, it's not a confusing number
20 return false;
21 }
22 // Update the transformed number with the flipped digit
23 transformedNumber = transformedNumber * 10 + digitTransformations[digit];
24 // Remove the last digit from the original number
25 originalNumber /= 10;
26 }
27 // The number is confusing if the transformed number is different from the original number
28 return transformedNumber != n;
29 }
30}
31
1class Solution {
2public:
3 // Function to check if a number is a confusing number
4 bool confusingNumber(int n) {
5 // Digit mapping, with -1 representing invalid mappings
6 vector<int> map = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
7 int originalNumber = n; // Store the original number
8 int transformedNumber = 0; // Initialize the transformed number
9
10 // Process each digit to create the transformed number
11 while (originalNumber) {
12 int digit = originalNumber % 10; // Get the last digit
13
14 // Digit is not valid if it cannot be mapped
15 if (map[digit] < 0) {
16 return false; // This is not a confusing number
17 }
18
19 // Build the transformed number by adding the mapped digit at the appropriate place
20 transformedNumber = transformedNumber * 10 + map[digit];
21
22 // Remove the last digit from the original number for next iteration
23 originalNumber /= 10;
24 }
25
26 // A number is confusing if it's not equal to the original number after transformation
27 return transformedNumber != n;
28 }
29};
30
1// Digit mapping, with undefined representing invalid mappings
2const digitMap: (number | undefined)[] = [0, 1, undefined, undefined, undefined, undefined, 9, undefined, 8, 6];
3
4// Function to check if a number is a confusing number
5function confusingNumber(n: number): boolean {
6 let originalNumber: number = n; // Store the original number
7 let transformedNumber: number = 0; // Initialize the transformed number
8
9 // Process each digit to create the transformed number
10 while (originalNumber > 0) {
11 const digit: number = originalNumber % 10; // Get the last digit
12
13 // The digit is not valid if it cannot be mapped (i.e., it is undefined in digitMap)
14 if (digitMap[digit] === undefined) {
15 return false; // This is not a confusing number
16 }
17
18 // Build the transformed number by adding the mapped digit at the appropriate place
19 transformedNumber = transformedNumber * 10 + digitMap[digit]!;
20
21 // Remove the last digit from the original number for the next iteration
22 originalNumber = Math.floor(originalNumber / 10);
23 }
24
25 // A number is confusing if it's not equal to the original number after transformation
26 return transformedNumber !== n;
27}
28
Time and Space Complexity
The time complexity of the given code is O(log n)
, where n
is the input number. This complexity arises because the code processes each digit of the number exactly once, and there are O(log n)
digits in a base-10 number.
The space complexity of the code is O(1)
since it uses a constant amount of extra space regardless of the input size. The variables x
, y
, and v
along with the array d
are the only allocations, and their size does not scale with n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first