एक सरणी arr[n] दी गई है, जिसमें n संख्या में पूर्णांक हैं और आकार को परिभाषित करने के लिए एक पूर्णांक k; कार्य आकार k के सभी उपअनुक्रमों का गुणनफल प्रिंट करना है, जिसमें न्यूनतम और अधिकतम तत्वों को छोड़कर।
मान लें हमारे पास 4 तत्वों का एक समुच्चय {1, 2, 3, 4} है और k 2 है तो इसके उपसमुच्चय होंगे − {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}
तो अधिकतम तत्व 4, और न्यूनतम तत्व 1 को छोड़कर, शेष तत्व होंगे −
2, 3, 3, 3, 2, जिनका गुणनफल होगा −
2 * 3 * 3 * 3 * 2 = 108
इसी तरह हमें समस्या हल करनी है
उदाहरण
इनपुट: arr[] = {3, 4, 1, 7}, k = 3 आउटपुट: 144 व्याख्या: उपसमुच्चय होंगे, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7} अधिकतम मान 7 और न्यूनतम 1 को हटाने पर हमें मिलेगा: {3, 4}, {4}, {3}, {3, 4}, इनका गुणा करने पर: 3 * 4 * 4 * 3 = 144 इनपुट: arr[] = {1, 2, 3, 4}, k = 3 आउटपुट: 36उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग कर रहे हैं −
समाधान प्राप्त करने के कई तरीके हो सकते हैं। एक दृष्टिकोण है जिसमें हम एक-एक करके सभी संभावित उपअनुक्रम उत्पन्न कर सकते हैं, और सेट के अधिकतम और न्यूनतम को छोड़कर सभी तत्वों का गुणनफल कर सकते हैं। हालांकि यह दृष्टिकोण प्राप्त करना आसान है लेकिन इसकी जटिलता बहुत अधिक है और दृष्टिकोण अक्षम है।
हमारे पास एक कुशल दृष्टिकोण भी है, इस दृष्टिकोण में हम पहले एक सरणी को क्रमबद्ध करेंगे, उपसमुच्चय या उपअनुक्रम को मान्यता दिए बिना या नहीं।
फिर हम एक-एक करके प्रत्येक तत्व की घटनाओं की संख्या गिनेंगे।
एक संख्या C(k-1) (n-1) उपअनुक्रमों में से C(k-1) (i) बार अधिकतम तत्व के रूप में और C(k-1) (n-i-1) बार उस उपअनुक्रम के न्यूनतम तत्व के रूप में हो सकती है।
अतः, हम कह सकते हैं कि यह अधिक कुशल दृष्टिकोण है क्योंकि iवां तत्व −
C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) बार होगा।
अब, हम सरणी में प्रत्येक तत्व के लिए x हल करेंगे, इसलिए इसका उत्तर गणना करना वास्तव में कठिन हो सकता है इसलिए हम फर्मेट के छोटे प्रमेय का उपयोग कर सकते हैं।
नोट − चूंकि उत्तर वास्तव में बड़ा हो सकता है इसलिए हम उत्तर को 10^9+7 के मॉड्यूलो में प्रिंट करेंगे।
एल्गोरिदम
शुरुआत चरण 1-> जोड़ी संयोजन की गणना करने के लिए फ़ंक्शन घोषित करें void pairs(int a, int b) int i, j घोषित करें लूप i = 0 से i <= a और i++ तक लूप j = 0 से j <= min(i, b) और j++ तक IF (j == 0 || j == i) c[i][j] = 1 सेट करें अंत अन्यथा c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val सेट करें अंत अंत अंत चरण 2-> घात के लिए फ़ंक्शन घोषित करें LL power(LL x, unsigned LL y) unsigned LL temp = 1 घोषित करें x = x % val सेट करें लूप जब तक (y > 0) IF(y & 1) temp = (temp * x) % val सेट करें अंत y = y >> 1 सेट करें x = (x * x) % val सेट करें अंत temp % val वापस करें चरण 3-> सभी उपअनुक्रमों के गुणनफल की गणना करने के लिए फ़ंक्शन घोषित करें unsigned LL product(LL arr[], int size, int k) unsigned LL temp = 1 घोषित करें और सेट करें sort(arr, arr + size) कॉल करके सरणी को क्रमबद्ध करें LL pow = c[size - 1][k - 1] घोषित करें और सेट करें लूप i = 0 से i < size और i++ तक LL pow_l = c[i][k - 1] घोषित करें और सेट करें LL pow_f = c[size - i - 1][k - 1] घोषित करें और सेट करें LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val घोषित करें और सेट करें unsigned LL mul = power(arr[i], pow_e) % val घोषित करें और सेट करें temp = ((temp % val) * (mul % val)) % val सेट करें अंत temp % val वापस करें चरण 4-> main() में pairs(100, 100) कॉल करें LL arr[] = { 3, 4, 1, 7 } घोषित करें और सेट करें आकार की गणना करें int size = sizeof(arr) / sizeof arr[0] int k = 3 घोषित करें और सेट करें unsigned LL temp = product(arr, size, k) घोषित करें और सेट करें temp प्रिंट करें रुकेंउदाहरण
#include <bits/stdc++.h> using namespace std; #define val 1000000007 #define LL long long #define max 101 LL c[max - 1][max - 1]; LL power(LL x, unsigned LL y) { unsigned LL temp = 1; x = x % val; while (y > 0) { if (y & 1) { temp = (temp * x) % val; } y = y >> 1; x = (x * x) % val; } return temp % val; } void pairs(int a, int b) { int i, j; for (i = 0; i <= a; i++) { for (j = 0; j <= min(i, b); j++) { if (j == 0 || j == i) c[i][j] = 1; else c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val; } } } // सभी उपअनुक्रमों के गुणनफल की गणना करने के लिए फ़ंक्शन unsigned LL product(LL arr[], int size, int k) { unsigned LL temp = 1; // सरणी क्रमबद्ध करना sort(arr, arr + size); LL pow = c[size - 1][k - 1]; for (int i = 0; i < size; i++) { LL pow_l = c[i][k - 1]; LL pow_f = c[size - i - 1][k - 1]; LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val; unsigned LL mul = power(arr[i], pow_e) % val; temp = ((temp % val) * (mul % val)) % val; } return temp % val; } int main() { // सभी जोड़ों का योग pairs(100, 100); LL arr[] = { 3, 4, 1, 7 }; int size = sizeof(arr) / sizeof arr[0]; int k = 3; unsigned LL temp = product(arr, size, k); cout<<"आकार k के सभी उपअनुक्रमों का गुणनफल न्यूनतम और अधिकतम तत्व को छोड़कर है : "<<temp << endl; return 0; }आउटपुट
आकार k के सभी उपअनुक्रमों का गुणनफल न्यूनतम और अधिकतम तत्व को छोड़कर है :144
