C++-এ একটি অ্যারেতে AP (পাটিগণিতের অগ্রগতি) অনুসারীর সংখ্যা

পূর্ণসংখ্যা উপাদান ধারণকারী একটি অ্যারে arr[] দেওয়া হয়েছে। লক্ষ্য হল arr[] এর ভিতরে পাটিগণিতের অগ্রগতির পরবর্তী সংখ্যা গণনা করা। arr[]-এর ভিতরে উপাদানের পরিসর হল [1,1000000]।

খালি ক্রম বা একক উপাদানও গণনা করা হবে।

আসুন উদাহরণ দিয়ে বোঝা যাক।

উদাহরণস্বরূপ

ইনপুট - arr[] ={1,2,3}

আউটপুট - একটি অ্যারেতে AP (পাটিগণিতের অগ্রগতি) অনুগামী সংখ্যাগুলি হল:8

ব্যাখ্যা - নিম্নলিখিত অনুসৃতিগুলি AP গঠন করবে:-

{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

ইনপুট - arr[] ={2,4,5,8}

আউটপুট - একটি অ্যারেতে AP (পাটিগণিতের অগ্রগতি) অনুগামী সংখ্যাগুলি হল:12

ব্যাখ্যা - নিম্নলিখিত অনুসৃতিগুলি AP গঠন করবে:-

{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, { 5,8}, {2,5,8}

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি

• একটি খালি ক্রমও একটি AP৷
৷
• একটি একক মানও একটি AP৷
৷
• অ্যারের মধ্যে max_val এবং min_val হিসাবে সর্বনিম্ন এবং সর্বোচ্চ মান খুঁজুন। সমস্ত AP অনুগামীতে সাধারণ পার্থক্য হবে [ min_val - max_val , max_val - min_val ]
• এখন প্রতিটি সাধারণ পার্থক্যের জন্য আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করে পরবর্তীগুলি খুঁজে পাব এবং arr_2[size] এ সংরক্ষণ করব।
• দৈর্ঘ্য 2 বা 2-এর বেশি কোনো অনুগামী arr_2[i]-1 এর যোগফল হবে না যেখানে i [0,2] এবং পার্থক্য হল D৷
• arr_2[i] =1+ যোগফল ( arr[j] ) যেখানে i
• দ্রুত পদ্ধতির জন্য arr_3[max_size]-এ যোগফল ( arr_2[j] এর সাথে arr[j]+D =arr[i] এবং j
• ইনপুট হিসাবে integer array arr[] নিন।
• ফাংশন AP_subsequence(int arr[], int size) একটি ইনপুট অ্যারে নেয় এবং একটি অ্যারেতে AP (পাটিগণিত অগ্রগতি) অনুসারীর গণনা প্রদান করে৷
• প্রাথমিক গণনাকে 0 হিসাবে নিন।
• পরবর্তী সংখ্যা সংরক্ষণের জন্য ভেরিয়েবল max_val, min_val, arr_2[size] নিন এবং যোগফল সংরক্ষণের জন্য arr_3[max_size] নিন।
• Traverse arr[] লুপ ব্যবহার করে সর্বাধিক এবং সর্বনিম্ন উপাদান খুঁজুন এবং max_val এবং min_val এ সংরক্ষণ করুন।
• একক উপাদান AP এবং খালি AP-এর জন্য গণনা =আকার +1 নিন।
• সর্বোচ্চ পার্থক্য গণনা করুন diff_max =max_val - min_val এবং diff_min =min_val - max_val যত সাধারণ পার্থক্য সম্ভব।
• j=0 থেকে j
• সেট arr_2[j] =1;
• এর জন্য arr[j] - i>=1 এবং arr[j] - i <=1000000 সেট arr_2[j] +=arr_3[arr[j] - i]।
• গণনার জন্য arr_2[j]-1 যোগ করুন।
• যোগফলকে arr_3[arr[j]] =arr_3[arr[j]] + arr_2[j] হিসাবে আপডেট করুন।
• শেষে ফলাফল হিসাবে গণনা করুন।

#include<bits/stdc++.h>

using namespace std;
#define max_size 10000

int AP_subsequence(int arr[], int size) {
   int count = 0;
   int max_val = INT_MAX;
   int min_val = INT_MIN;
   int arr_2[size];
   int arr_3[max_size];

   for (int i = 0; i < size; i++) {
      max_val = min(max_val, arr[i]);
      min_val = max(min_val, arr[i]);
   }
   count = size + 1;
   int diff_max = max_val - min_val;
   int diff_min = min_val - max_val;
   for (int i = diff_max; i <= diff_min; i++) {
      memset(arr_3, 0, sizeof arr_3);
      for (int j = 0; j < size; j++) {
         arr_2[j] = 1;
         if (arr[j] - i >= 1) {
            if (arr[j] - i <= 1000000) {
               arr_2[j] += arr_3[arr[j] - i];
            }
         }
         count += arr_2[j] - 1;
         arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
      }
   }
   return count;
}
int main() {
   int arr[] = {1,1,6,7,8};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
   return 0;
}

Count of AP (Arithmetic Progression) Subsequences in an array are: 17