Cho một mảng arr [n], chứa n số nguyên và một số nguyên k để xác định kích thước; nhiệm vụ là in sản phẩm của tất cả các dãy con có kích thước k ngoại trừ các phần tử tối thiểu và tối đa.
Giả sử chúng ta có tập hợp 4 phần tử {1, 2, 3, 4} và k là 2 để các tập con của nó sẽ là - {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}
Vì vậy, loại trừ phần tử tối đa 4 và phần tử tối thiểu 1, các phần tử còn lại sẽ là -
2, 3, 3, 3, 2, sản phẩm sẽ là -
2 * 3 * 3 * 3 * 2 =108
Tương tự như vậy, chúng tôi phải giải quyết vấn đề
Ví dụ
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 Phương pháp tiếp cận mà chúng tôi đang sử dụng để giải quyết vấn đề trên -
Có thể có nhiều cách để đạt được giải pháp. Có một cách tiếp cận trong đó chúng ta có thể tạo ra tất cả các dãy con có thể có từng dãy một và tích tất cả các phần tử ngoại trừ giá trị lớn nhất và tối thiểu của tập hợp. Mặc dù cách tiếp cận này dễ thực hiện nhưng có độ phức tạp rất cao và cách tiếp cận này không hiệu quả.
Chúng tôi cũng có một cách tiếp cận hiệu quả, trong cách tiếp cận này, trước tiên chúng tôi sẽ sắp xếp một mảng, bỏ qua các tập con hoặc tập con có được xem xét hay không.
Sau đó, chúng tôi sẽ đếm số lần xuất hiện của từng phần tử một.
Một số có thể xảy ra C (k-1) (n-1) dãy con trong đó C (k-1) (i) lần chúng ta sẽ xuất hiện tối đa phần tử C (k-1) (n-i-1) lần nó sẽ xảy ra là phần tử tối thiểu của dãy con đó.
Do đó, chúng tôi có thể nói rằng đây là cách tiếp cận hiệu quả hơn vì phần tử thứ i sẽ xuất hiện -
C (k-1) (n-1) - C (k-1) (i) - C (k-1) (n-i-1) lần.
Bây giờ, trước tiên chúng ta sẽ giải x cho mỗi phần tử trong arr [i], vì vậy câu trả lời của nó có thể thực sự khó tính vì vậy chúng ta có thể sử dụng Định lý Fermat’s Little.
Lưu ý −Vì câu trả lời có thể rất lớn nên chúng tôi sẽ in câu trả lời trong mod của 109 + 7.
Thuật toán
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 Ví dụ
#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;
} Đầu ra
product of all subsequences of size k except minimum and maximum element is :144