MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Integer Replacement

Written By ## 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.

Input: 102
Output: 152

#### Example 2

Input: 1022 Output: 1522

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.

``````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``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where n is the number of digits in the input number. When iterating through the digits of the number using the modulus operator, the number of iterations is directly proportional to the number of digits in the input number.
• Space Complexity: O(1) as no extra space is required.