# 397 Integer Replacement

## 397. [Integer Replacement](https://leetcode.com/problems/integer-replacement/description/)

## 1. Question

Given a positive integernand you can do operations as follow:

1. If n is even, replace n with`n/2`.
2. If n is odd, you can replace n with either`n+ 1`or`n- 1`.

What is the minimum number of replacements needed fornto become 1?

**Example 1:**

```
Input:
8

Output:
3

Explanation:
8 ->4 ->2 ->1
```

**Example 2:**

```
Input:

7


Output:

4


Explanation:

7 ->8 ->4 ->2 ->1
or
7 ->6 ->3 ->2 ->1
```

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public int integerReplacement(int n) {
        Set<Long> visited = new HashSet();
        Queue<Long> queue = new LinkedList();

        visited.add((long)n);
        queue.add((long)n);

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                long curNum = queue.remove();

                if (curNum == 1) {
                    return level;
                }

                if (curNum % 2 == 0 && visited.add(curNum / 2)) {
                    queue.add(curNum / 2);
                }
                else {
                    if (visited.add(curNum + 1)) {
                        queue.add(curNum + 1);
                    }

                    if (visited.add(curNum - 1)) {
                        queue.add(curNum - 1);
                    }
                }
            }
            ++level;
        }
        return level;
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度?, 空间复杂度?
