Input:
8
Output:
3
Explanation:
8 ->4 ->2 ->1
Input:
7
Output:
4
Explanation:
7 ->8 ->4 ->2 ->1
or
7 ->6 ->3 ->2 ->1
class Solution {
public int integerReplacement(int n) {
Queue<Long> queue = new LinkedList<>();
Set<Long> visited = new HashSet<>();
queue.add((long)n);
visited.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.contains(curNum / 2)) {
queue.add(curNum / 2);
visited.add(curNum / 2);
}
else {
if (!visited.contains(curNum + 1)) {
queue.add(curNum + 1);
visited.add(curNum + 1);
}
if (!visited.contains(curNum - 1)) {
queue.add(curNum - 1);
visited.add(curNum - 1);
}
}
}
++level;
}
return -1;
}
}