The Reverse Integer problem is a programming challenge that asks you to reverse the digits of a given integer. For example, if you’re given the number 123, you should return the number 321.

Now, it’s important to note that there are a few rules to keep in mind while solving this problem. For one, you need to make sure that your solution can handle negative integers. So, if you’re given the number -123, your solution should return -321.

Another thing to keep in mind is that your solution shouldn’t include any leading zeros. That means that if you’re given the number 120, your solution should return the number 21 (not 021).

Finally, it’s worth noting that this problem can be solved using a variety of programming languages, and there are many different approaches you can take to arrive at the correct solution. Some possible strategies include using string manipulation, iteration, or recursion.

Solutions for Reverse Integer

Solution 1: Using string manipulation

One approach to solving this problem is to convert the integer to a string, reverse the string, and then convert the reversed string back to an integer. Here’s the pseudocode:

function reverseInteger(num):
  // convert the integer to a string
  strNum = convertToString(num)
  
  // reverse the string
  reversedStrNum = reverseString(strNum)
  
  // convert the reversed string back to an integer
  reversedNum = convertToInteger(reversedStrNum)
  
  return reversedNum

Let’s break down each step in this solution:

  • First, we convert the given integer num to a string using the convertToString function.
  • Next, we reverse the string using the reverseString function.
  • Finally, we convert the reversed string back to an integer using the convertToInteger function and return the result.

Here’s an example implementation of this solution in Python:

def reverseInteger(num):
    strNum = str(num)
    reversedStrNum = strNum[::-1]
    reversedNum = int(reversedStrNum)
    return reversedNum

Time Complexity: O(n), where n is the number of digits in the input integer. This is because the solution involves converting the integer to a string, reversing the string, and then converting it back to an integer, each of which takes O(n) time.

See also  Leetcode 463 Island Perimeter Solved

Space Complexity: O(n), where n is the number of digits in the input integer. This is because the solution requires creating a string of length n to hold the reversed integer.

Code Complexity: This solution is relatively simple and straightforward, as it only involves a few string manipulation operations.

Solution 2: Using iteration

Another approach to solving this problem is to use iteration to extract the digits of the given integer one by one and append them in reverse order to a new integer. Here’s the pseudocode:

function reverseInteger(num):
  // initialize the reversed integer to zero
  reversedNum = 0
  
  // iterate through the digits of the input integer
  while num != 0:
    // extract the last digit of the input integer
    digit = num % 10
    
    // append the digit to the reversed integer
    reversedNum = (reversedNum * 10) + digit
    
    // remove the last digit from the input integer
    num = num // 10
  
  return reversedNum

Let’s break down each step in this solution:

  • First, we initialize a new variable reversedNum to zero, which will eventually hold the reversed integer.
  • Next, we use a while loop to iterate through the digits of the input integer num.
  • Inside the loop, we extract the last digit of num using the modulo operator %, and append it to reversedNum by multiplying it by 10 and adding it to the current value of reversedNum.
  • We then remove the last digit from num using integer division //, which effectively shifts the decimal point one place to the left.
  • We repeat this process until num becomes zero, at which point we return reversedNum.

Here’s an example implementation of this solution in Python:

def reverseInteger(num):
    reversedNum = 0
    while num != 0:
        digit = num % 10
        reversedNum = (reversedNum * 10) + digit
        num = num // 10
    return reversedNum

Time Complexity: O(n), where n is the number of digits in the input integer. This is because the solution involves iterating through each digit of the input integer, which takes O(n) time.

See also  Write a program to find the number of days between two dates

Space Complexity: O(1), because the solution only requires a constant amount of space to hold the reversedNum variable.

Code Complexity: This solution is slightly more complex than the previous solution, as it involves a while loop and some arithmetic operations. However, it’s still relatively straightforward.

Solution 3: Using recursion

A third approach to solving this problem is to use recursion to reverse the integer. We can use the fact that we can get the last digit of the integer by taking the remainder when dividing by 10, and that we can remove the last digit by dividing by 10. Here’s the pseudocode:

function reverseInteger(num):
  // base case: return num if it's a single digit
  if num < 10 and num > -10:
    return num
  
  // recursive case: reverse the digits of the remaining integer
  // and append the last digit

Time Complexity: O(n), where n is the number of digits in the input integer. This is because the solution involves recursively calling the function once for each digit in the input integer, which takes O(n) time.

Space Complexity: O(n), because the solution requires creating n stack frames for the recursive calls.

Code Complexity: This solution is the most complex of the three, as it involves recursion and a bit more logic to extract the last digit and remove it from the integer.

String Manipulation vs Iterative vs Recursive: Which one is better?

In terms of time complexity, all three solutions have the same worst-case time complexity of O(n). However, the second solution has the best space complexity, while the first and third solutions both have O(n) space complexity. In terms of code complexity, the first solution is the simplest, followed by the second and then the third.

I would say that the second solution using iteration is the most efficient and simplest solution, as it has O(n) time complexity, O(1) space complexity, and relatively simple code. However, the choice of solution may depend on other factors, such as the programming language being used or the specific requirements of the problem.

See also  Detect loop in linked list using Floyd's algorithm

Reverse Integer in Java:

public int reverse(int x) {
    int reversedNum = 0;
    while (x != 0) {
        int digit = x % 10;
        reversedNum = (reversedNum * 10) + digit;
        x /= 10;
    }
    return reversedNum;
}

This solution is very similar to the pseudocode I provided earlier. We initialize a variable reversedNum to zero, and then use a while loop to extract each digit of the input integer x and append it to reversedNum. To extract the digit, we use the modulo operator %, and to remove the digit, we use integer division /=. Finally, we return reversedNum.

Reverse Integer in JavaScript:

function reverse(x) {
    let reversedNum = 0;
    while (x !== 0) {
        let digit = x % 10;
        reversedNum = (reversedNum * 10) + digit;
        x = Math.trunc(x / 10);
    }
    return reversedNum;
}

This solution is very similar to the Java solution, with a few differences. We use the let keyword to declare variables instead of int. We also use the !== operator to compare x to zero, and we use the Math.trunc function to remove the decimal part of the result of dividing x by 10.

Reverse Integer in Ruby:

def reverse(x)
    reversed_num = 0
    while x != 0
        digit = x % 10
        reversed_num = (reversed_num * 10) + digit
        x /= 10
    end
    return reversed_num
end

This solution is very similar to the Java solution as well. We use the def keyword to define a function, and we use while and end to define the loop. We use x /= 10 to remove the digit, and we return reversed_num.

Reverse Integer in Python:

def reverse(x):
    reversedNum = 0
    while x != 0:
        digit = x % 10
        reversedNum = (reversedNum * 10) + digit
        x //= 10
    return reversedNum

This solution is almost identical to the Java solution, with a few small differences. We use def to define the function, and we use //= instead of /= to remove the digit. We also use return instead of reversedNum at the end.