Integer Replacement (Interview Solution)

How to Solve Integer Replacement

Integer Replacement Introduction

The Integer Replacement question involves replacing all the digits ‘0’ with ‘5’ in a given integer. The trick to this problem is to use the mod operator '%' to pop the last number and check for 0's until we've gone through the full number and then remember to reverse it at the end.

Integer Replacement Problem

Given an integer as an input, replace all the digits ‘0’ with ‘5’ in the integer.

Example 1

Input: 102
Output: 152

Example 2

Input: 1022
Output: 1522

Example 3

Input: 1020
Output: 1525

Integer Replacement Solutions

To solve the problem of replacing '0's with '5's in a given number, we iterate through each digit of the number. For each digit, we check if it is '0' and replace it with '5' if necessary. We build a new number by multiplying the previous value by 10 and adding the modified digit. Finally, we reverse the new number to get the desired result. Handling special cases, such as when the number is 0 or negative, is also taken into account to ensure correctness. By following these steps, the algorithm replaces '0's with '5's and returns the modified number.

Python Implementation

def replace_zeros_with_fives(num):
    # When input number is 0
    if num == 0:
        return 5

# Variable to store reversed number with 0s turned to 5s
    temp = 0

# Flag for if the number is negative
    is_negative = False

# Check if the number is negative
    if num < 0:
        is_negative = True
        num = abs(num)  # Convert negative number to positive to calculate

# Iterate through each digit in the number using modulus 10 to pop the last number
    while num > 0:
        digit = num % 10

# Replace 0 with 5, otherwise keep the digit as it is
        if digit == 0:
            digit = 5

# Build the temp number by multiplying by 10 and adding the digit
        temp = temp * 10 + digit

# Remove the last digit from the number
        num //= 10

# Reverse the temp number to get the final result
    result = 0
    while temp > 0:
        digit = temp % 10
        result = result * 10 + digit
        temp //= 10

# Convert the result to negative if the original number was negative
    if is_negative:
        result = -result

return result

num1 = 102
print(replace_zeros_with_fives(num1))  # Output: 152

num2 = 1020
print(replace_zeros_with_fives(num2))  # Output: 1525

Java Implementation

public int replaceZerosWithFives(int num) {
    // When input number is 0
    if (num == 0) return 5;

// Variable to store reversed number with 0s turned to 5s
    int temp = 0;

// Flag for if the number is negative
    boolean isNegative = false;

// Check if the number is negative
    if (num < 0) {
        isNegative = true;
        num = Math.abs(num);  // Convert negative number to positive if necessary
    }

// Iterate through each digit in the number using modulus 10 to pop the last number
    while (num > 0) {
        int digit = num % 10;

// Replace 0 with 5, otherwise keep the digit as is
        if (digit == 0) {
            digit = 5;
        }

// Build the temp number by multiplying by 10 and adding the digit
        temp = temp * 10 + digit;

// Remove the last digit from the number
        num /= 10;
    }

// Reverse the temp number to get the final result
    int result = 0;
    while (temp > 0) {
        int digit = temp % 10;
        result = result * 10 + digit;
        temp /= 10;
    }

// Convert the result to negative if the original number was negative
    if (isNegative) {
        result = -result;
    }

return result;
}

Time/Space Complexity Analysis