Jobs

Interviews

Discussions

A Number After a Double Reversal

Easy

Asked by:

19 views

Reversing an integer means to reverse all its digits.

For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer num, reverse num to get reversed1, then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

0 <= num <= 10⁶

Try coding it in LeetCode

A Number After a Double Reversal

Easy

Asked by:

19 views

Reversing an integer means to reverse all its digits.

For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer num, reverse num to get reversed1, then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

0 <= num <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input number, num, be negative?
Can the input number, num, be zero?
What is the expected range of values for the input number, num?
If the reversed number has leading zeros, should those leading zeros be removed before the second reversal?
Are there any specific data type constraints for the input (e.g., integer, long)?

Brute Force Solution

Approach

The core idea is to simulate the reversal process exactly as described. We will reverse the number, reverse it again, and then check if the final number is the same as the original number. This method directly implements the problem's instructions.

Here's how the algorithm would work step-by-step:

First, reverse the digits of the given number.
Then, reverse the digits of the reversed number from the previous step.
Finally, compare the twice-reversed number with the original number.
If they are the same, the answer is yes; otherwise, the answer is no.

Code Implementation

def is_same_after_double_reversal(original_number: int) -> bool:

    # Convert the integer to a string for easier reversal
    number_string = str(original_number)

    # Reverse the digits of the number
    reversed_number_string = number_string[::-1]

    # Convert the reversed string back to an integer.
    # This handles cases where the reversed number has leading zeros.
    reversed_number = int(reversed_number_string)

    # Convert the reversed number back to a string for the second reversal.
    reversed_number_string_again = str(reversed_number)

    # Reverse the digits again.
    twice_reversed_number_string = reversed_number_string_again[::-1]

    # Convert the twice reversed number back to an integer.
    twice_reversed_number = int(twice_reversed_number_string)

    # Compare the twice-reversed number with the original number
    return twice_reversed_number == original_number

Big(O) Analysis

Time Complexity

O(log n) – The algorithm reverses the digits of the number twice. Reversing the digits involves iterating through each digit of the number. The number of digits in a number n is proportional to log(n). Therefore, reversing once is O(log n), and reversing twice is also O(log n). The comparison at the end takes constant time. Hence, the overall time complexity is O(log n).

Space Complexity

O(N) – The provided explanation involves reversing the digits of the number, implying the use of a string or array to store the digits for manipulation. Reversing a number of N digits requires creating a reversed representation that takes up space proportional to the number of digits, N. Therefore the space complexity depends on the size of the input number represented by the number of digits N, leading to O(N) space. This is because we essentially need a temporary space to store the reversed number which depends on the input number of digits

Optimal Solution

Approach

The goal is to determine if reversing a number twice results in the original number. The key insight is that leading zeros are removed after the first reversal, which can affect the second reversal. Therefore, we only need to check if the number has a trailing zero.

Here's how the algorithm would work step-by-step:

Check if the given number ends in zero.
If the number is zero, then reversing it twice will result in the same number.
If the number is not zero and ends in zero, reversing it once will remove the trailing zero(s). Reversing it again will not result in the original number.
If the number does not end in zero, reversing it twice will result in the same original number.

Code Implementation

def is_same_after_reversals(number) -> bool:
    # Zero is a special case; reversing it twice results in the same number.
    if number == 0:
        return True

    # Check if the number has trailing zeros.
    if number % 10 == 0:

        # If a number ends in zero, the reversed number will lose that zero and not be equal after being reversed twice.
        return False

    # Numbers without trailing zeros will be the same after two reversals.
    return True

Big(O) Analysis

Time Complexity

O(1) – The provided solution checks only a single condition: whether the number ends in zero. This check involves a constant-time operation (examining the last digit). Regardless of the size of the input number, the number of operations remains constant. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The provided algorithm primarily uses conditional checks and does not create any auxiliary data structures that scale with the input number N. No temporary lists, hash maps, or significant recursive calls are involved. The space used is constant, regardless of the number of digits in the input. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Number is zero	Reversing zero results in zero; handle zero explicitly by returning true only if the original number was zero.
Number is negative	Reversing a negative number can lead to sign issues, convert number to absolute before reversal, apply negative sign if necessary and compare absolute values.
Number ends with zero(s)	Reversing removes trailing zeros, which affects the final result; explicitly check for and handle the removal of trailing zeros after the first reversal.
Integer overflow during reversal	Check for potential overflow during reversal; return false immediately if the reversed value exceeds the maximum integer value or falls below the minimum integer value.
Single-digit number	A single-digit number's reversal is the same as itself; return true if the original number is the same as the number after the double reversal.
Number is close to the maximum integer value	Multiplication during the reversal process may result in overflow; carefully check and handle potential overflow situations.
Number with leading zeros (represented as string)	If the input is a string, trim the leading zeros before processing to ensure correct reversal result.
Maximum integer value	Reversing the maximum integer value may result in overflow; handle these cases before reversing

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input number, num, be negative?
Can the input number, num, be zero?
What is the expected range of values for the input number, num?
If the reversed number has leading zeros, should those leading zeros be removed before the second reversal?
Are there any specific data type constraints for the input (e.g., integer, long)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, reverse the digits of the given number.
Then, reverse the digits of the reversed number from the previous step.
Finally, compare the twice-reversed number with the original number.
If they are the same, the answer is yes; otherwise, the answer is no.

Code Implementation

def is_same_after_double_reversal(original_number: int) -> bool:

    # Convert the integer to a string for easier reversal
    number_string = str(original_number)

    # Reverse the digits of the number
    reversed_number_string = number_string[::-1]

    # Convert the reversed string back to an integer.
    # This handles cases where the reversed number has leading zeros.
    reversed_number = int(reversed_number_string)

    # Convert the reversed number back to a string for the second reversal.
    reversed_number_string_again = str(reversed_number)

    # Reverse the digits again.
    twice_reversed_number_string = reversed_number_string_again[::-1]

    # Convert the twice reversed number back to an integer.
    twice_reversed_number = int(twice_reversed_number_string)

    # Compare the twice-reversed number with the original number
    return twice_reversed_number == original_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Check if the given number ends in zero.
If the number is zero, then reversing it twice will result in the same number.
If the number is not zero and ends in zero, reversing it once will remove the trailing zero(s). Reversing it again will not result in the original number.
If the number does not end in zero, reversing it twice will result in the same original number.

Code Implementation

def is_same_after_reversals(number) -> bool:
    # Zero is a special case; reversing it twice results in the same number.
    if number == 0:
        return True

    # Check if the number has trailing zeros.
    if number % 10 == 0:

        # If a number ends in zero, the reversed number will lose that zero and not be equal after being reversed twice.
        return False

    # Numbers without trailing zeros will be the same after two reversals.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Number is zero	Reversing zero results in zero; handle zero explicitly by returning true only if the original number was zero.
Number is negative	Reversing a negative number can lead to sign issues, convert number to absolute before reversal, apply negative sign if necessary and compare absolute values.
Number ends with zero(s)	Reversing removes trailing zeros, which affects the final result; explicitly check for and handle the removal of trailing zeros after the first reversal.
Integer overflow during reversal	Check for potential overflow during reversal; return false immediately if the reversed value exceeds the maximum integer value or falls below the minimum integer value.
Single-digit number	A single-digit number's reversal is the same as itself; return true if the original number is the same as the number after the double reversal.
Number is close to the maximum integer value	Multiplication during the reversal process may result in overflow; carefully check and handle potential overflow situations.
Number with leading zeros (represented as string)	If the input is a string, trim the leading zeros before processing to ensure correct reversal result.
Maximum integer value	Reversing the maximum integer value may result in overflow; handle these cases before reversing