পাইথনে ইন্টিজারকে শূন্য করার ন্যূনতমワン-বিট অপারেশন খুঁজে বের করার প্রোগ্রাম

আমাদের একটি সংখ্যা n আছে, আমাদের এটিকে ০-এ রূপান্তর করতে হবে নিচের অপারেশনগুলো যেকোনো সংখ্যক বার ব্যবহার করে:

n-এর বাইনারি রিপ্রেজেন্টেশনে ডানপাশের বিটটি সিলেক্ট করুন।
n-এর বাইনারি রিপ্রেজেন্টেশনে i-তম বিট পরিবর্তন করুন যখন (i-1)-তম বিট ১ সেট করা থাকে এবং (i-2) থেকে ০তম বিটগুলো ০ সেট করা থাকে।

শেষে আমাদের n-কে ০-এ রূপান্তর করার ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট n = 6 হলে আউটপুট হবে 4 কারণ প্রাথমিক 6 = "110", তারপর দ্বিতীয় অপারেশন দিয়ে "010", তারপর প্রথম অপারেশন দিয়ে "011", তারপর দ্বিতীয় অপারেশন দিয়ে "001" এবং শেষে প্রথম অপারেশন দিয়ে "000"।

সমাধানের ধাপসমূহ (গ্রে কোড / বাইনারি রিফ্লেকশন)

n := n-এর বাইনারি বিটের লিস্ট
m := একটি নতুন লিস্ট
last := 0
n-এর প্রতিটি d এর জন্য:
- যদি last == 1 হয়, তবে d := 1 - d
- last := d
- d-কে m-এর শেষে যোগ করুন
m-এর এলিমেন্টগুলো যোগ করে বাইনারি সংখ্যা বানান
ডেসিমাল ফরমে রিটার্ন করুন

উদাহরণ

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

def solve(n):
    n = list(map(int, bin(n)[2:]))
    m = []
    last = 0
    for d in n:
        if last == 1:
            d = 1 - d
        last = d
        m.append(d)
    m = ''.join(map(str, m))
    return int(m, 2)

n = 6
print(solve(n))