<prompt> Kwa kupewa nambari kamili n, rudisha _safu_ ans _ya urefu_ n 1 _kama kwamba kwa kila_ i 0 i n_,_ ansi _ni idadi ya_ 1_s katika uwakilishi jozi ya_ i.Mfano wa 1:Ingizo: n 2Pato: 0,1,1Maelezo:0 -- 01 -- 12 - 10Mfano wa 2:Ingizo: n 5Pato: 0,1,1,2,1,2Maelezo:0 -- 01 -- 12 - 103 -- 114 -- 1005 -- 101Vikwazo: 0 n 105Fuatilia: Ni rahisi sana kupata suluhu na muda wa kukimbia wa On log n. Unaweza kuifanya kwa wakati wa mstari On na ikiwezekana kwa kupita moja? Je, unaweza kuifanya bila kutumia kitendakazi chochote kilichojengewa ndani yaani, kama __builtin_popcount katika C?  <response>: chatudef countBitsn: ans 0 n 1 kwa i katika masafa 1, n 1: ansi ansi i - 1 1 kurudi ansmaelezoAlgoriti huleta uchunguzi muhimu: i i - 1 ina uwakilishi wa mfumo wa jozi sawa na i, lakini ikiwa 1 kidogo imeondolewa. Hii husababisha njia ya haraka na bora ya kuhesabu idadi ya biti 1 katika uwakilishi jozi wa kila nambari katika safu 0, n.Kwa kila nambari i katika safu 1, n, tunakokotoa ansi kulingana na ansi i - 1. Kwa kuwa ansi i - 1 ni hesabu ya biti 1 katika uwakilishi wa jozi ya i i - 1, kuongeza 1 kwa hesabu hiyo itatupa hesabu. ya biti 1 katika uwakilishi jozi ya i.Kanuni inarudia kupitia safu 1, n na kujaza safu ya towe ans ipasavyo. Safu ya mwisho ans ina hesabu ya biti 1 katika uwakilishi jozi ya kila nambari katika safu 0, n.Utata wa saa wa algoriti hii ni On inaporudiarudia mfululizo 1, n mara moja tu, na uchangamano wa nafasi ni On 1 kwa kuwa huunda safu ya urefu n 1 kuhifadhi matokeo. 