public class Solution {
public int integerReplacement(int n) {
assert n > 0;
Queue<Long> queue = new LinkedList<>();
queue.offer((long)n);
return bfs(queue, 0);
}
private int bfs(Queue<Long> oldqueue, int level) {
Queue<Long> newqueue = new LinkedList<>();
while (!oldqueue.isEmpty()) {
long n = oldqueue.poll();
if (n == 1) {
return level;
}
if (n % 2 == 0) {
newqueue.offer(n / 2);
} else {
newqueue.offer(n + 1);
newqueue.offer(n  1);
}
}
return bfs(newqueue, level + 1);
}
}
Java BFS solution, tail recursion


@dachuan.huang
Good solution,
mine is similar to yours, why leetcode is giving me Memory Limit Exceeds for n = 2147483647 though

@milegedan Oh, whenever you see a number 2147483647, you should directly think overflow, and then you should directly change "int" to "long" :)