N থেকে M-এ যেতে ন্যূনতম ধাপের সংখ্যা বের করা C++-তে

মনে করুন আমাদের দুটি পূর্ণসংখ্যা N এবং M আছে। আমাদের N থেকে M-এ যেতে ন্যূনতম ধাপের সংখ্যা বের করতে হবে, নিচের অপারেশনগুলো করে -

সংখ্যা x কে ২ দিয়ে গুণ করুন, তাহলে x হবে 2*x
সংখ্যা x থেকে ১ বিয়োগ করুন, তাহলে সংখ্যা হবে x - 1

যদি N = 4 এবং M = 6, তবে আউটপুট হবে 2। তাই যদি অপারেশন নম্বর ২ N-এ করি, তবে N হবে 3, তারপর অপারেশন নম্বর ১ আপডেটেড N-এ করি, তবে সেটি হবে 2 * 3 = 6। তাই ন্যূনতম ধাপের সংখ্যা হবে 2।

এই সমস্যাটি সমাধানের জন্য, আমরা নিচের নিয়মগুলো অনুসরণ করব -

আমরা সমস্যাটি উল্টে দিতে পারি, মানে N নেওয়া যাক M থেকে শুরু করে, তাহলে নতুন দুটি অপারেশন হবে
- সংখ্যাকে ২ দিয়ে ভাগ করুন, যখন এটি জোড়,
- সংখ্যার সাথে ১ যোগ করুন
এখন ন্যূনতম অপারেশন সংখ্যা হবে
- যদি N > M, তবে তাদের পার্থক্য রিটার্ন করুন, তাহলে ধাপের সংখ্যা হবে M-এ ১ যোগ করা, যতক্ষণ না সেটি N-এর সমান হয়
- অন্যথায় যখন N < M, M-কে ২ দিয়ে ভাগ করে যান, যতক্ষণ না সেটি N-এর চেয়ে ছোট হয়। যদি M বিজোড় হয়, তবে প্রথমে ১ যোগ করুন, তারপর ২ দিয়ে ভাগ করুন। একবার M N-এর চেয়ে ছোট হলে, তাদের পার্থক্য কাউন্টের সাথে যোগ করুন।

উদাহরণ

#include <iostream>
using namespace std;

int countMinimumSteps(int n, int m) {
    int count = 0;
    while (m > n) {
        if (m % 2 == 1) {
            m++;
            count++;
        }
        m /= 2;
        count++;
    }
    return count + n - m;
}

int main() {
    int n = 4, m = 6;
    cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
}

আউটপুট

Minimum number of operations required: 2