পাথর সরিয়ে কনsekutিভ পজিশনে আনা II C++-এ

অনন্ত সংখ্যারেখায় কিছু পাথর আছে। প্রতিটি টার্নে একটি এন্ডপয়েন্ট পাথর (সর্বোচ্চ বা সর্বনিম্ন পজিশন)কে এমন একটি খালি পজিশনে সরাতে হয় যাতে সেটি আর এন্ডপয়েন্ট না হয়। খেলটি থামবে যখন পাথরগুলো কনsekutিভ পজিশনে আসে। ন্যূনতম এবং সর্বোচ্চ মুভ সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট: [7, 3, 9]

আউটপুট: [1, 3]

অ্যালগরিদম

1. অ্যারে সর্ট করুন।
2. সর্বোচ্চ মুভ (max moves): max(a[n-2]-a[0], a[n-1]-a[1]) - (n-2)
3. ন্যূনতম মুভ (min moves):
   • স্লাইডিং উইন্ডো ব্যবহার করে এমন উইন্ডো খুঁজুন যেখানে n-১টি পাথর ফিট হয়।
   • বাইরের পাথরগুলো সরিয়ে আনতে হবে।
   • বিশেষ কেস: যদি n-১টি পাথর ইতিমধ্যে কনsekutিভ হয় কিন্তু শেষটি দূরে থাকে, তবে ২ মুভ লাগে।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector numMovesStonesII(vector& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        
        // Max moves
        int maxMoves = max(stones[n-2] - stones[0], stones[n-1] - stones[1]) - (n - 2);
        
        // Min moves - sliding window
        int minMoves = n;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j + 1 < n && stones[j+1] - stones[i] < n) j++;
            int inside = j - i + 1;
            if (inside == n - 1 && stones[j] - stones[i] == n - 2)
                minMoves = min(minMoves, 2);
            else
                minMoves = min(minMoves, n - inside);
        }
        
        return {minMoves, maxMoves};
    }
};

int main() {
    Solution ob;
    vector v = {7, 3, 9};
    auto ans = ob.numMovesStonesII(v);
    cout << "[" << ans[0] << ", " << ans[1] << "]";
    return 0;
}

ইনপুট

[7, 3, 9]

আউটপুট

[1, 3]