পাইথনে Single Number II সমস্যা সমাধান

মনে করুন আমাদের একটি নন-এমপ্টি ইন্টিজার অ্যারে আছে, যেখানে প্রতিটি এলিমেন্ট তিনবার আসে ছাড়া একটি, যা ঠিক একবার আসে। আমাদের সেই একক এলিমেন্টটি খুঁজে বের করতে হবে। উদাহরণস্বরূপ, অ্যারে যদি [2,2,3,2] হয়, তবে আউটপুট হবে 3।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

অ্যারে থেকে এলিমেন্টগুলোর অ্যাবসোলিউট ভ্যালু নিয়ে সর্বোচ্চ সংখ্যা বের করুন এবং max_num-এ সংরক্ষণ করুন।
max_bits := integer of (log max_num base 2) + 2
list1 := size max_bits এর একটি খালি লিস্ট যার এলিমেন্টগুলো ০
প্রতিটি num in nums জন্য:
- pos := 0
- while num != 0 and pos < max_bits
  - যদি num বিজোড় হয়, তবে list1[pos] ১ বাড়ান।
  - n := n / 2 এবং pos ১ বাড়ান।
for i in range 0 to max_bits
- list1[i] := list1[i] mod 3
pos := 0, res := 0
for i in range max_bits
- যদি list1[i] != 0 হয়, তবে result := result + 2^pos
- pos := pos + 1
যদি list1[max_bits - 1] == 1 হয়, তবে res := -(2^max_bits - res)
return res

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

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