Codility - SparseBinaryDecomposition

Đề Codility đưa cho bạn một số N, và yêu cầu tìm Q sao cho cả Q lẫn N - Q đều là số nhị phân “thưa” — tức không có hai bit 1 nào nằm cạnh nhau. Nghe đơn giản, nhưng nếu bạn duyệt hết mọi Q từ 0 đến N thì với N cỡ hàng tỷ, bài sẽ timeout ngay lập tức.

Cách thoát ra là dùng toán tử bitwise để gỡ trực tiếp các cặp bit 1 liền kề, thay vì brute-force. Bài viết này đi qua cách kiểm tra một số có “thưa” hay không, cách tìm Q, kèm code chạy được và giải thích từng kết quả.

1. Sparse Binary Decomposition là gì?

Khái niệm quan trọng

Sparse Binary (nhị phân thưa): số nhị phân không có hai bit 1 đứng cạnh nhau.
Ví dụ:
- Hợp lệ: 1010 (thập phân 10), 1001 (9)
- Không hợp lệ: 1100 (12), 1011 (11)

Sparse Binary Decomposition là bài toán tách N thành hai phần cùng “thưa”: tìm Q ≤ N sao cho Q là Sparse Binary và P = N - Q cũng là Sparse Binary. Nếu không tìm được, trả về -1.

2. Cách tiếp cận bài toán

2.1. Phân tích từng bước

Ý tưởng chung: thay vì thử mọi Q, ta quét các bit của N từ phải sang trái và xử lý ngay khi gặp cặp bit 1 liền kề.

Kiểm tra một số có “thưa” không: đọc từng bit. Gặp bit 0 thì dịch phải 1 bước. Gặp bit 1 mà bit kế bên cũng là 1 thì số đó không thưa; ngược lại, dịch phải 2 bước để bỏ qua cả cặp 1–0 vừa xét.
Tìm Q ≤ N là Sparse Binary: nếu N chưa thưa, ta “tắt” bit cao hơn của mỗi cặp 1 liền kề — tức trừ N đi 2 ** (vị_trí + 1). Làm vậy chắc chắn cho ra một số nhỏ hơn N và không còn hai bit 1 cạnh nhau.
Kiểm tra phần dư P: tính P = N - Q. Nếu P cũng thưa, Q chính là đáp án; nếu không, trả về -1.

2.2. Lỗi thường gặp và cách khắc phục

Lặp vô hạn: đây là bẫy hay gặp nhất. Trong vòng while (N), nếu có nhánh nào không dịch bit thì N không bao giờ về 0 và chương trình treo cứng. Lưu ý: đây không phải stack overflow — lỗi đó chỉ xảy ra khi đệ quy quá sâu hoặc thiếu điểm dừng, còn vòng while không làm đầy Call Stack.
Cách khắc phục:
- Đảm bảo mọi nhánh trong vòng lặp đều dịch bit (N >>= 1 hoặc N >>= 2) để N tiến dần về 0.
- Đặc biệt chú ý nhánh continue: rất dễ quên dịch bit trước khi nhảy sang vòng kế tiếp.

3. Ví dụ mã nguồn và giải thích

Dưới đây là một đoạn mã minh họa. Tên biến và hàm dùng tiếng Anh để dễ đọc và tái sử dụng.

// Quét bit từ phải sang trái, dừng ngay khi thấy hai bit 1 liền kề.
// N = 0 không vào vòng lặp, nên 0 được coi là "thưa" — đúng như mong đợi.
function checkIsBinarySparse(N) {
  while (N) {
    // Bit hiện tại là 0 → an toàn, xét bit kế tiếp
    if ((N & 1) === 0) {
      N >>= 1;
      continue;
    }
    // Bit hiện tại là 1 mà bit kế bên cũng là 1 → không thưa
    if ((N >> 1) & 1) return false;
    // Cặp "1 rồi 0" hợp lệ → nhảy qua cả hai bit
    N >>= 2;
  }
  return true;
}

// Tìm số thưa lớn nhất mà thuật toán quét được, luôn ≤ N.
function findSparseNumber(N) {
  const original = N;
  let currentBit = 0;
  // Tổng giá trị của những bit 1 mà ta sẽ tắt đi
  let bitsToTurnOff = 0;

  while (N) {
    if ((N & 1) === 0) {
      currentBit += 1;
      N >>= 1;
      continue;
    }
    // Gặp cặp bit 1 liền kề → tắt bit cao hơn của cặp, tức bit (currentBit + 1)
    if ((N >> 1) & 1) {
      bitsToTurnOff += 2 ** (currentBit + 1);
    }
    currentBit += 2;
    N >>= 2;
  }

  // Trừ một lần duy nhất ở cuối, thay vì sửa N trong lúc đang quét
  return original - bitsToTurnOff;
}

function execute(N) {
  const Q = checkIsBinarySparse(N) ? N : findSparseNumber(N);
  const P = N - Q;

  // P = 0 vẫn hợp lệ, vì 0 là số thưa
  return checkIsBinarySparse(P) ? Q : -1;
}

// Ví dụ minh họa
console.log(execute(24)); // 8  → Q = 1000,  P = 16 (10000)
console.log(execute(20)); // 20 → Q = 10100, P = 0
console.log(execute(10)); // 10 → Q = 1010,  P = 0
console.log(execute(5)); //  5  → Q = 101,   P = 0

Giải thích ngắn gọn:

checkIsBinarySparse(N): quét bit từ phải sang trái, trả về false ngay khi bắt gặp hai bit 1 liền kề. Với N = 0 vòng lặp không chạy lần nào và hàm trả về true — chi tiết nhỏ này quan trọng, bạn sẽ thấy lý do ở mục 3.2.
findSparseNumber(N): mỗi lần gặp cặp bit 1 liền kề tại vị trí currentBit, nó cộng dồn 2 ** (currentBit + 1) vào bitsToTurnOff — đúng bằng giá trị của bit cao hơn trong cặp. Hàm không sửa N trực tiếp (nó chỉ dịch N để duyệt), nên mọi thao tác “tắt bit” được gom lại rồi trừ một lần ở cuối: original - bitsToTurnOff.
execute(N): lấy Q = N nếu N đã thưa, ngược lại gọi findSparseNumber. Sau đó kiểm tra P = N - Q; thưa thì trả Q, không thì trả -1.

3.1. Lần theo `bitsToTurnOff` với `N = 27`

bitsToTurnOff là biến dễ gây bối rối nhất, nên hãy chạy tay một lượt với N = 27 (11011):

Vị trí bit	Bit hiện tại	Bit kế bên	Hành động	`bitsToTurnOff`
0	`1`	`1`	Cặp liền kề → tắt bit 1, cộng `2 ** 1 = 2`	`2`
2	`0`	—	Bit `0`, dịch phải và đi tiếp	`2`
3	`1`	`1`	Cặp liền kề → tắt bit 4, cộng `2 ** 4 = 16`	`18`

Kết quả: Q = 27 - 18 = 9. Kiểm chứng bằng nhị phân — từ 11011, ta tắt bit 1 và bit 4, còn lại 01001 = 9, đúng là số thưa. Phần dư P = 27 - 9 = 18 (10010) cũng thưa, nên execute(27) trả về 9.

Điểm mấu chốt: bitsToTurnOff không phải “số lượng bit”, mà là tổng giá trị thập phân của các bit cần tắt — nhờ vậy chỉ cần một phép trừ duy nhất là xong.

3.2. Kết quả hiển thị

execute(24) → 8. Vì 24 (11000) có cặp 1 liền kề ở vị trí bit 3 và 4, hàm trừ đi 2 ** 4 = 16, còn Q = 8 (1000). Phần dư P = 24 - 8 = 16 (10000) cũng thưa, nên 8 là đáp án hợp lệ.
execute(20) → 20. Số 20 (10100) vốn đã thưa nên Q = N và P = 0. Đây là lúc chi tiết “0 được coi là thưa” phát huy tác dụng: không có bit 1 nào thì đương nhiên không thể có hai bit 1 cạnh nhau, và hàm trả về Q thay vì -1.
Tương tự, execute(10) → 10 (1010) và execute(5) → 5 (101), đều là các số đã thưa sẵn.

4. Kết quả thực tế

5. Ứng dụng thực tế

Nói thẳng: bạn sẽ hiếm khi cần tách một số thành hai số nhị phân thưa trong code hằng ngày. Nhưng dạng biểu diễn “không có hai bit 1 liền kề” thì không hề vô dụng — nó chính là Non-Adjacent Form (NAF), được dùng trong mã hóa đường cong elliptic để giảm số phép cộng điểm khi nhân vô hướng. Ít bit 1 liền kề đồng nghĩa với ít phép tính hơn.

Thứ bạn thật sự mang đi được từ bài này là kỹ năng quét bit:

Xử lý cờ (flags) bằng bitmask: cùng một tư duy N & 1, N >>= 1 để đọc từng quyền hạn, từng trạng thái nén trong một số nguyên — nhanh hơn và gọn hơn nhiều so với mảng boolean.
Nhận ra các mẫu bit quen thuộc: nhiều thao tác tưởng cần cả vòng lặp lại gói gọn trong một phép toán (xem ví dụ ngay bên dưới).
Viết vòng lặp bit an toàn: mọi nhánh đều phải dịch bit, nếu không N sẽ không bao giờ về 0 và chương trình treo cứng.

Hai mẫu bit đáng thuộc lòng, thử với 12 (1100) và 10 (1010):

// Mẫu 1: n & (n - 1) → tắt bit 1 thấp nhất
// 12 = 1100
// 11 = 1011  (chính là 12 - 1)
// AND  1000  → 8
console.log(12 & (12 - 1)); // 8

// Mẫu 2: n & (n >> 1) → khác 0 nghĩa là CÓ hai bit 1 liền kề
// 12 = 1100        10 = 1010
// >>1  0110        >>1  0101
// AND  0100 → 4    AND  0000 → 0
console.log(12 & (12 >> 1)); // 4 (khác 0) → 12 không thưa
console.log(10 & (10 >> 1)); // 0          → 10 thưa

// Nhờ mẫu 2, cả vòng while trong checkIsBinarySparse rút lại còn một dòng:
const isSparse = (n) => (n & (n >> 1)) === 0;

console.log(isSparse(10)); // true
console.log(isSparse(11)); // false  (1011 có cặp 1 liền kề)
console.log(isSparse(0)); //  true   (không có bit 1 nào)

Mẫu 2 hoạt động vì n >> 1 đẩy mọi bit sang phải một vị trí. Nếu bit i và bit i+1 của n cùng bằng 1, sau khi dịch chúng sẽ chồng lên nhau tại vị trí i, và phép AND giữ lại đúng bit đó — cho ra kết quả khác 0.

Lưu ý

Khi thử brute-force mọi N từ 0 đến 100.000, luôn tồn tại cặp Q và P hợp lệ — nghĩa là nhánh return -1 gần như không bao giờ chạy. Cứ giữ nó cho đúng yêu cầu đề bài, nhưng đừng ngạc nhiên nếu không test case nào chạm tới.

Vậy là bạn đã hiểu cách dùng bitwise để tách một số thành hai phần nhị phân thưa, thay vì brute-force qua từng giá trị Q. Điểm mấu chốt là quét bit từ phải sang trái và xử lý ngay khi gặp cặp 1 liền kề — chỉ một lượt duyệt, độ phức tạp O(log N). Lần tới gặp bài toán thao tác bit, hãy thử hỏi: liệu có mẫu bit nào giải quyết trong một phép toán duy nhất không?