পাইথনে একই সেট বিট সংখ্যায় পরের বড় সংখ্যা বের করার প্রোগ্রাম

ধরা যাক একটি সংখ্যা n দেওয়া আছে; আমাদের n-এর বাইনারি রিপ্রেজেন্টেশনে যতগুলো ১ (সেট বিট) আছে, उतনোই ১ கொண்ட পরের ছোটো বড় সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট: n = 7

আউটপুট: 11

ব্যাখ্যা: ৭-এর বাইনারি 0111 (৩টি ১)। ৭-থেকে বড় সংখ্যার মধ্যে ৩টি ১ থাকা সবচেয়ে ছোট সংখ্যা ১১ যেটির বাইনারি 1011।

সমাধানের ধাপসমূহ

1. copy := n, zeros := 0, ones := 0
<লি>copy != 0 এবং copy জোড় (লেস্ট সিগনিফিক্যান্ট বিট ০) থাকা পর্যন্ত:
• zeros += 1
• copy >>= 1
2. copy বিজোড় (লেস্ট সিগনিফিক্যান্ট বিট ১) থাকা পর্যন্ত:
   • ones += 1
   • copy >>= 1
3. right := ones + zeros
4. n |= 1 << right
5. n &= ~((1 << right) - 1)
6. n |= (1 << (ones - 1)) - 1
7. n ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, n):
        copy = n
        zeros = 0
        ones = 0
        while copy and not (copy & 1):
            zeros += 1
            copy >>= 1
        while copy & 1:
            ones += 1
            copy >>= 1
        right = ones + zeros
        n |= 1 << right
        n &= ~((1 << right) - 1)
        n |= (1 << (ones - 1)) - 1
        return n

ob = Solution()
n = 7
print(ob.solve(n))

ইনপুট

7

আউটপুট

11