मान लीजिए हमारे पास पूर्णांकों का एक नॉन-खाली ऐरे है, प्रत्येक एलिमेंट तीन बार प्रकट होता है सिवाय एक के, जो ठीक एक बार प्रकट होता है। हमें एकल एलिमेंट ढूंढना है। इसलिए यदि ऐरे [2,2,3,2] है तो आउटपुट 3 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
ऐरे के एलिमेंट्स के एब्सोल्यूट मान को लेकर अधिकतम संख्या ढूंढें और इसे max_num में स्टोर करें
max_bits := (log max_num आधार 2 का पूर्णांक) + 2
list1 := आकार max_bits की एक खाली लिस्ट जिसके एलिमेंट्स 0 हैं
nums में प्रत्येक num के लिए -
pos := 0
जब तक num 0 नहीं है और pos < max_bit
यदि no विषम है, तो list1[pos] को 1 से बढ़ाएं
n := n / 2 और pos को 1 से बढ़ाएं
i को 0 से max_bits तक रेंज में
list1[i] := list1[i] mod 3
pos := 0, res := 0
i को max_bits तक रेंज में
यदि list1[i] 0 नहीं है, तो result := result + 2^pos
pos := pos + 1
यदि list1[max_bits - 1] 1 है, तो res := -(2^max_bits - res)
res लौटाएं
उदाहरण (पायथन)
बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -
import math
class Solution(object):
def singleNumber(self, nums):
max_num = max(map(abs, nums))
max_bits = (int)(math.log(max_num,2)) + 2
list1 = [0 for i in range(max_bits)]
for no in nums:
pos = 0
while (no != 0 and pos < max_bits):
if (no & 1 != 0):
list1[pos] += 1
no >>= 1
pos += 1
for i in range(max_bits):
list1[i] %= 3
pos = 0
result = 0
for i in range(max_bits):
if (list1[i] != 0):
result += (2 ** pos)
pos += 1
print (list1, max_bits)
if (list1[max_bits - 1] == 1):
result = -(2 ** max_bits - result)
return (result)
ob = Solution()
print(ob.singleNumber([2,2,3,2]))इनपुट
[2,2,3,2]
आउटपुट
[1, 1, 0] 3 3