Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Counting Bits

Problem (yeniden ifade)

0..n dahil her i için, i’nin ikili gösterimindeki 1-bit sayısını döndür.

Sezgi

Sağa kaydırma LSB’yi düşürür; (i & 1) geri eklenir. Daha küçük cevapları yeniden kullanır → toplam O(n).

Yaklaşımlar

DP: dp[i] = dp[i>>1] + (i&1)

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. dp[i] = dp[i & (i-1)] + 1 ile eşdeğer (popcount yinelemesi).

Adım adım. n=5 → [0,1,1,2,1,2].

Trade-off’lar. Sayı başına Brian Kernighan en kötü O(n log n).

Çözüm

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

Şablon bağlantısı

Bit DP / popcount tablosu.

Yansıma

dp[i] = dp[i>>1] + (i&1). Kaydırma bir biti atar, son bit tekse 1 eklenir.
dp[0] = 0. n = 0 cevap [0]. n = 1 cevap [0, 1].
Her i önceki bir sayının bitlerine bakar. Döngü 1’den n’e.