C++-এ অ্যারের শেষে পৌঁছানোর জন্য জাম্প করার পদ্ধতির সংখ্যা গণনা

একটি ধনাত্মক সংখ্যার অ্যারে দেওয়া আছে। প্রতিটি এলিমেন্ট নির্দেশ করে সেটি ইনডেক্স থেকে সর্বোচ্চ কতগুলো জাম্প করা যায় অ্যারেতে শেষে পৌঁছানোর জন্য। লক্ষ্য হলো প্রতিটি এলিমেন্ট থেকে শেষে পৌঁছানোর জন্য কতগুলো জাম্প পদ্ধতি আছে সেটি বের করা। যদি arr[] = [1,2,3] হয়, তবে ১-এর জন্য জাম্প ১, ২-এর জন্য জাম্প ১ বা ২, এবং ৩-এর জন্য জাম্প ১, ২ বা ৩ হতে পারে।

উদাহরণ ১

ইনপুট

arr[] = {1,2,3}

আউটপুট

অ্যারের শেষে পৌঁছানোর জন্য জাম্প করার পদ্ধতির সংখ্যা: 1 1 0

ব্যাখ্যা

১-এর জন্য জাম্প: ১, ২-এর জন্য জাম্প ১ বা ২, শেষে পৌঁছাতে শুধু ১ জাম্প ১ দরকার। ৩-এর জন্য জাম্প ১,২ অথবা ৩, এটা শেষে আছে তাই কোনো জাম্প দরকার নেই।

উদাহরণ ২

ইনপুট

arr[] = {4,3,6,2}

আউটপুট

অ্যারের শেষে পৌঁছানোর জন্য জাম্প করার পদ্ধতির সংখ্যা: 4 2 1 0

ব্যাখ্যা

৪-এর জন্য জাম্প: ১, ২, ৩ বা ৪। শেষে পৌঁছাতে শুধু ১,২ বা ৩ দরকার। পদ্ধতিগুলো: ৪-৩-৬-২, ৪-৬-২, ৪-২, ৪-৩-২। মোট ৪। ৩-এর জন্য জাম্প ১, ২ বা ৩। শেষে পৌঁছাতে উভয় দরকার। পদ্ধতি: ৩-৬-২, ৩-২। মোট ২। ৬-এর জন্য জাম্প ১ থেকে ৫, শেষে পৌঁছাতে ১ দরকার। পদ্ধতি: ৬-২। মোট ১। ২-এর জন্য জাম্প ১ বা ২, এটা শেষে আছে তাই কোনো জাম্প দরকার নেই।

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে প্রতিটি এলিমেন্ট arr[i]-এর জন্য সেটির আগে থাকা সকল এলিমেন্ট যেগুলো শেষে পৌঁছাতে পারে এবং বর্তমান এলিমেন্ট থেকে যেগুলো erreichযোগ্য, সেসব এলিমেন্টের পদ্ধতির কাউন্ট যোগ করা হয়। এছাড়া ১ যোগ করা হয় যদি arr[i] থেকে এক জাম্পে সরাসরি শেষে পৌঁছানো যায়।

• ইন্টিজার অ্যারে arr[] নিন।

• reach_end(int arr[], int size) ফাংশনটি অ্যারে গ্রহণ করে শেষে পৌঁছানোর পদ্ধতির সংখ্যা রিটার্ন করে।

• arr_2[] অ্যারে নিন প্রতিটি এলিমেন্ট থেকে শেষে পৌঁছানোর পদ্ধতি সংরক্ষণের জন্য।

• memset(arr_2, 0, sizeof(arr_2)) দিয়ে পুরো arr_2[] ০ দিয়ে আরম্ভ করুন।

• for লুপ দিয়ে i=size-2 থেকে i=0 পর্যন্ত arr[] ট্রুভার্স করুন (শেষ এলিমেন্ট বিবেচনা করা হয় না)।

• temp = size - i - 1 নিন। যদি temp >= arr[i] হয় তবে এক জাম্পে সরাসরি শেষে পৌঁছানো যায়। arr_2[i]++ দিয়ে পদ্ধতি বাড়ান।

• এখন সকল এলিমেন্ট যারা শেষে পৌঁছাতে পারে এবং যাদের বর্তমান এলিমেন্ট থেকে পৌঁছানো যায়, সেসব এলিমেন্টের পদ্ধতির কাউন্ট arr_2[i]-এ যোগ করুন।

• উপরোক্ত কাজের জন্য for লুপ দিয়ে j=i+1 থেকে j এবং j<=arr[i]+i পর্যন্ত ট্রুভার্স করুন। যদি কোনো arr[j] -১ না হয়, তবে সেটি arr_2[i]-এ যোগ করুন।

• যদি এখনও arr_2[i] ০ থাকে, তবে সেটিকে -১ সেট করুন, অর্থাৎ সেটি থেকে শেষে পৌঁছানো সম্ভব নয়।

• সকল লুপ শেষে arr_2[]-এ প্রতিটি এলিমেন্টের জন্য শেষে পৌঁছানোর পদ্ধতি থাকবে।

• for লুপ দিয়ে arr_2 প্রিন্ট করুন ফলাফল হিসেবে।

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

void reach_end(int arr[], int size) {
    int arr_2[size]; 
    memset(arr_2, 0, sizeof(arr_2)); 
    
    for (int i = size-2; i >= 0; i--) {
        int temp = size - i - 1; 
        if (arr[i] >= temp) {
            arr_2[i]++; 
        } 
        
        for (int j = i+1; j < size-1 && j <= arr[i] + i; j++) {
            if (arr_2[j] != -1) {
                arr_2[i] = arr_2[i] + arr_2[j]; 
            } 
        } 
        
        if(arr_2[i] == 0) {
            arr_2[i] = -1; 
        } 
    } 
    
    cout << "অ্যারের শেষে পৌঁছানোর জন্য জাম্প করার পদ্ধতির সংখ্যা: "; 
    for (int i=0; i < size; i++) {
        cout << arr_2[i] << " "; 
    } 
} 

int main() { 
    int arr[] = {2, 3, 7, 1, 8, 9}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    reach_end(arr, size); 
    return 0; 
}

অ্যারের শেষে পৌঁছানোর জন্য জাম্প করার পদ্ধতির সংখ্যা: 8 5 3 1 1 0