Beautiful Arrangement:
Cho các số từ 1 đến num. Một "beautiful arrangement" là mảng thỏa mãn: tại vị trí i (1 ≤ i ≤ N), số tại i chia hết cho i HOẶC i chia hết cho số tại i.
Vấn đề
Cần viết hàm JS nhận số num, trả về số lượng beautiful arrangement có thể xây dựng.
Ví dụ:
const input = 2
Kết quả:
const output = 2
Giải thích:
[1,2] và [2,1] đều thỏa mãn.
Ví dụ
Mã thực hiện:
const num = 4; const countArrangements = (num = 1) => { let ans = 0 const recur = (curr, vis) => { if (curr === 1){ ans++; }else{ for (let i = num; i; i--) { let possible = (i % curr === 0 || curr % i === 0); let visited = vis & 1 << i; if (possible && !visited){ recur(curr-1, vis | 1 << i); } } } }; recur(num, 0); return ans; }; console.log(countArrangements(num));
Giải thích code:
Dùng biến kết quả ans và hàm đệ quy duyệt các nhánh. Hàm đệ quy nhận: số đang đặt (curr) và bitmask vị trí đã dùng (vis).
Kết quả
Kết quả in ra console:
8