ลดตัวเลขให้เหลือ 1 ด้วยการหาร 2 หรือ +/- 1 (Integer Replacement) ใน JavaScript

ปัญหา

รับ num ทำซ้ำ: คู่ → หาร 2, คี่ → +1 หรือ -1 หาจำนวนขั้นตอนน้อยที่สุดจนเหลือ 1

ตัวอย่าง

const num = 7;

7→8→4→2→1 (4 ขั้นตอน) หรือ 7→6→3→2→1 (4 ขั้นตอน) → 4

โค้ดตัวอย่าง (BFS + Memoization)

const num = 7; 
const downToOne = (num = 1) => { 
  let min = Number.POSITIVE_INFINITY; 
  let stack = [{ num: num, step: 0 }]; 
  let set = new Set(); 
  let next, item; 
  while (stack.length) { 
    item = stack.shift(); 
    if (item.num === 1) { if (min > item.step) min = item.step; continue; } 
    if (set.has(item.num) || item.step >= min) continue; 
    set.add(item.num); 
    next = item.step + 1; 
    if (item.num % 2 === 0) { stack.push({ num: item.num / 2, step: next }); } 
    else { stack.push({ num: item.num - 1, step: next }); stack.push({ num: item.num + 1, step: next }); } 
  } 
  return min; 
}; 
console.log(downToOne(num));

ผลลัพธ์

4