एक सरणी एआर [एन] दिया गया है, जिसमें 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
इसी तरह हमें समस्या का समाधान करना होगा
उदाहरण
Input: arr[] = {3, 4, 1, 7}, k = 3
Output: 144
Explanation: subset will be, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
Eliminating maximum value 7 and minimum 1 we will get:
{3, 4}, {4}, {3}, {3, 4}, so multiplying these will give us:
3 * 4 * 4 * 3 = 144
Input: arr[] = {1, 2, 3, 4}, k = 3
Output: 36 उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग कर रहे हैं -
समाधान प्राप्त करने के कई तरीके हो सकते हैं। एक दृष्टिकोण है जिसमें हम एक-एक करके सभी संभावित परिणाम उत्पन्न कर सकते हैं, और सेट के अधिकतम और न्यूनतम को छोड़कर सभी तत्वों को उत्पादित कर सकते हैं। हालांकि यह दृष्टिकोण हासिल करना आसान है लेकिन इसमें बहुत अधिक जटिलता है और यह दृष्टिकोण अक्षम है।
हमारे पास एक कुशल दृष्टिकोण भी है, इस दृष्टिकोण में हम सबसे पहले एक सरणी को सॉर्ट करेंगे, सबसेट या अनुवर्ती पर विचार करने के लिए या नहीं।
फिर हम एक-एक करके प्रत्येक तत्व के घटित होने की संख्या की गणना करेंगे।
एक संख्या सी (के -1) (एन -1) के बाद हो सकती है जिसमें से सी (के -1) (i) बार हम अधिकतम तत्व सी (के -1) (एन-आई -1) बार घटित होंगे उस बाद के न्यूनतम तत्व के रूप में।
इसलिए, हम कह सकते हैं कि यह अधिक कुशल दृष्टिकोण है क्योंकि ith तत्व घटित होगा -
C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) बार।
अब, पहले हम arr[i] में प्रत्येक तत्व के लिए x को हल करेंगे, इसलिए इसका उत्तर गणना करना वास्तव में कठिन हो सकता है इसलिए हम Fermat's Little Theorem का उपयोग कर सकते हैं।
नोट −चूंकि उत्तर वास्तव में बड़ा हो सकता है इसलिए हम उत्तर को 109+7 मोड में प्रिंट करेंगे।
एल्गोरिदम
Start
Step 1-> Declare function to calculate the pairs combination
void pairs(int a, int b)
Declare int i, j
Loop For i = 0 and i <= a and i++
Loop For j = 0 and j <= min(i, b) and j++
IF (j == 0 || j == i)
Set c[i][j] = 1
End
Else
Set c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val
End
End
End
Step 2-> declare function for power
LL power(LL x, unsigned LL y)
Declare unsigned LL temp = 1
Set x = x % val
Loop While (y > 0)
IF(y & 1)
Set temp = (temp * x) % val
End
Set y = y >> 1
Set x = (x * x) % val
End
return temp % val
Step 3-> Declare function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k)
Declare and set unsigned LL temp = 1
Call function to sort an array as sort(arr, arr + size)
Declare and set as LL pow = c[size - 1][k - 1]
Loop For i = 0 and i < size and i++
Declare and set LL pow_l = c[i][k - 1]
Declare and set LL pow_f = c[size - i - 1][k - 1]
Declare and set LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val
Declare and set unsigned LL mul = power(arr[i], pow_e) % val
Set temp = ((temp % val) * (mul % val)) % val
End
return temp % val
Step 4-> In main()
Call pairs(100, 100)
Declare and set LL arr[] = { 3, 4, 1, 7 }
Calculate size as int size = sizeof(arr) / sizeof arr[0]
Declare and set int k = 3
Declare and set unsigned LL temp = product(arr, size, k)
Print temp
Stop उदाहरण
#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;
}
}
}
//function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k) {
unsigned LL temp = 1;
//sorting array
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() {
// sum of all the pairs
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<<"product of all subsequences of size k except minimum and maximum element is :"<<temp << endl;
return 0;
} आउटपुट
product of all subsequences of size k except minimum and maximum element is :144