অ্যারে ডিরেঞ্জমেন্ট গণনা C++-এ

সমস্যা বিবরণ

১ থেকে n পর্যন্ত সংখ্যা সাজানো একটি অ্যারে দেওয়া আছে। এর ডিরেঞ্জমেন্ট (derangement) সংখ্যা বের করতে হবে। ডিরেঞ্জমেন্ট = এমন পারমুটেশন যেখানে কোনো এলিমেন্ট তার অরিজিনাল পজিশনে থাকে না। ফলাফল 10^9+7 দিয়ে মডুলো।

উদাহরণ

n = 3 → অরিজিনাল: [1,2,3]

ডিরেঞ্জমেন্ট: [2,3,1] এবং [3,1,2] → আউটপুট: 2

অ্যালগরিদম: DP রিকারেন্স

D(n) = (n-1) * (D(n-1) + D(n-2))

বেস: D(1) = 0, D(2) = 1

প্রুফ: প্রথম এলিমেন্টকে n-1 ভাবে জায়গা দিয়ে বাকি দুই কেসে ভাগ করা যায়।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9 + 7;

lli add(lli a, lli b) { return (a + b) % MOD; }
lli mul(lli a, lli b) { return (a * b) % MOD; }

class Solution {
public:
    int findDerangement(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;
        vector<lli> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = mul(i - 1, add(dp[i-1], dp[i-2]));
        }
        return dp[n];
    }
};

int main() {
    Solution ob;
    cout << ob.findDerangement(3); // আউটপুট: 2
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n) — একবার লুপ।
• স্থান জটিলতা: O(n) — DP অ্যারে (O(1)-এও করা যায়)।