मान लीजिए हमारे पास एक गैर-ऋणात्मक पूर्णांक संख्या num है। 0 ≤ i ≤ num रेंज में प्रत्येक संख्या i के लिए हमें उनके बाइनरी समकक्ष में 1 की संख्या की गणना करनी होगी और उन्हें एक सूची के रूप में वापस करना होगा। इसलिए यदि संख्या 5 है, तो संख्याएं [0, 1, 2, 3, 4, 5] हैं, और इन संख्याओं में 1 की संख्या [0, 1, 1, 2, 1, 2] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- res := एक सरणी जो num + 1 संख्या के 0 रखती है
- offset := 0
- i के लिए 1 से num + 1 तक रेंज में
- यदि i और i - 1 = 0, तो res[i] := 1 और offset := 0
- अन्यथा offset को 1 से बढ़ाएं और res[i] := 1 + res[offset]
- res लौटाएं
उदाहरण (पाइथन)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class Solution: def countBits(self, num): result = [0] * (num+1) offset = 0 for i in range(1,num+1): if i & i-1 == 0: result[i] = 1 offset = 0 else: offset+=1 result[i] = 1 + result[offset] return result ob1 = Solution() print(ob1.countBits(6))
इनपुट
6
आउटपुट
[0, 1, 1, 2, 1, 2, 2]
