### View *Integer Replacement* on LeetCode

## Statistics

**Time Spent Coding**

16 minutes

**Time Complexity**

O(log(n)) - For the majority of iterations, `n`

is divided in half, resulting in the O(log(n)) time complexity.

**Space Complexity**

O(1) - The number of variables created is independent of n, resulting in the O(1) space complexity. If the recursive function calls count towards the space complexity, then it would be O(2 * log(n)) -> O(log(n)) since Big-O ignores constant multiples of the growth rate.

## Explanation

**This solution is not the most optimal, but arguably it is the most intuitive. The most optimal solutions utilize bit manipulation and are complex to understand and create on-demand**

Creating the recursive function requires a base case and logic to reduce its inputs.

The base case is `if n==1: return 0`

because 1 is the number `n`

needs to reach.

The other conditional statements determine which operation will get `n`

to 1 the fastest.

`if n%2==0:`

If the number is a factor of 2, then to get`n`

to 1 as fast as possible,`n`

should be divided by 2.`else:`

Otherwise,`n`

is odd and must be incremented or decremented to become a factor of 2. This can be done by performing both the incrementation and decrementation and returning the smallest.

The algorithm continuously loops through the base case and the conditional statements until the correct result is returned.

## Algorithm Used

**Recursion -** A function which calls itself contains a base case and logic that decreases the received inputs.

The base case is when n==1, and every other case recursively calls `integerReplacement`

until `n`

is reduced to 1.

## Solution

1
2
3
4
5
6
7
8
9
10

class Solution:
def integerReplacement(self, n: int) -> int:
if n==1: return 0
if n%2==0:
return self.integerReplacement(n//2)+1
else:
add=self.integerReplacement(n+1)
minus=self.integerReplacement(n-1)
return min(add,minus)+1