एक सरणी arr[] दी गई है जिसमें पूर्णांक तत्व हैं। लक्ष्य arr[] के अंदर अंकगणितीय श्रेणी (AP) सबसीक्वेंस की संख्या गिनना है। 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+ sum ( arr[j] ) जहां i<j और arr_2[j] + D= arr_2[i]
- तेज़ दृष्टिकोण के लिए योग ( arr_2[j] जहां arr[j]+D = arr[i] और j<i ) को arr_3[max_size] में जोड़ें
- इनपुट के रूप में पूर्णांक सरणी arr[] लें।
- फ़ंक्शन AP_subsequence(int arr[], int size) एक इनपुट सरणी लेता है और सरणी में AP (अंकगणितीय श्रेणी) सबसीक्वेंस की संख्या लौटाता है।
- प्रारंभिक गिनती 0 लें।
- सबसीक्वेंस गिनती संग्रहीत करने के लिए वेरिएबल max_val, min_val, arr_2[size] और योग संग्रहीत करने के लिए arr_3[max_size] लें।
- for लूप का उपयोग करके arr[] को पार करें और अधिकतम और न्यूनतम तत्व खोजें और max_val और min_val में स्टोर करें।
- count = size +1 लें एकल तत्व APs और खाली AP के लिए।
- अधिकतम अंतर diff_max = max_val - min_val और diff_min = min_val - max_val की गणना करें संभावित सामान्य अंतर के रूप में।
- for लूप का उपयोग करके j=0 से j<size तक पार करें।
- arr_2[j] = 1 सेट करें;
- arr[j] - i >= 1 और 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]।
- अंत में परिणाम के रूप में count लौटाएं।
उदाहरण
#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