একটি অ্যারে দেওয়া হয়েছে 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
একইভাবে আমাদের সমস্যার সমাধান করতে হবে
উদাহরণ
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 উপরের সমস্যা সমাধানের জন্য আমরা যে পদ্ধতি ব্যবহার করছি −
সমাধান অর্জনের অনেক উপায় থাকতে পারে। একটি পদ্ধতি আছে যেখানে আমরা একের পর এক সমস্ত সম্ভাব্য অনুসৃতি তৈরি করতে পারি এবং সেটের সর্বাধিক এবং সর্বনিম্ন ব্যতীত সমস্ত উপাদান তৈরি করতে পারি। যদিও এই পদ্ধতিটি অর্জন করা সহজ কিন্তু এর জটিলতা অনেক বেশি এবং পদ্ধতিটি অকার্যকর।
আমাদের একটি দক্ষ পন্থাও রয়েছে, এই পদ্ধতিতে আমরা প্রথমে একটি অ্যারে সাজাব, উপসেট বা পরবর্তী বিবেচনা করা বা না করাকে উপেক্ষা করে৷
তারপর আমরা একে একে প্রতিটি উপাদানের উপস্থিতির সংখ্যা গণনা করব।
একটি সংখ্যা ঘটতে পারে C(k-1) (n-1) পরবর্তী ক্রম যার মধ্যে C(k-1) (i)বার আমরা সর্বাধিক উপাদান C(k-1) (n-i-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
