397 Integer Replacement

397. Integer Replacement

1. Question

Given a positive integernand you can do operations as follow:

1. If n is even, replace n withn/2.

2. If n is odd, you can replace n with eithern+ 1orn- 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

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: 时间复杂度?, 空间复杂度?