338. Counting Bits
Tags:
Easy
Skills:
Bitwise
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu: Với một số nguyên không âm n , hãy trả về một mảng ans có độ dài n + 1, trong đó ans[i] là số lượng bit 1 trong biểu diễn nhị phân của i (với 0 ≤ i ≤ n)
Phân tích và ý tưởng
Có nhiều cách giải tối ưu nhất là sử dụng DP kết hợp với thao tác bit:
- Nhận xét: Số lượng bit 1 của i có thể tính từ bit 1 của i >> 1 (tức là i dịch phải 1 bit, tương đương với chia 2 lấy phần nguyên)
- Nếu i là số chẵn, bit cuối là 0, nên số bit 1 của i bằng số bit 1 của i /2
- Nếu i là số lẻ, bit cuối là 1, nên số bit 1 của i bằng số bit 1 của i / 2 cộng thêm 1
Solution
typescripttypescript
1function countBits(n: number): number[] {
2 const ans: number[] = Array(n + 1).fill(0);
3 for (let i = 1; i <= n; i++) {
4 ans[i] = ans[i >> 1] + (i & 1);
5 }
6 return ans;
7};