Depend of pairs whose sum of pairwise product with X and Y is Ok

[ad_1]

Given an array arr[] of measurement N and three integers X, Y and Ok, the duty is to depend the variety of pairs (i, j) the place i < j such that (arr[i] * X + arr[j] * Y) = Ok.

Examples:

Enter: arr[] = {3, 1, 2, 3}, X = 4, Y = 2, Ok = 14
Output: 2
Rationalization: The doable pairs are: (1, 2), (3, 4).
For i = 1, j = 2, Worth of the expression = 4 * 3 + 2 * 1 = 14.
For i = 3, j = 4, Worth of the expression = 4 * 2 + 2 * 3 = 14.

Enter: arr[] = [1, 3, 2], X = 1, Y = 3, Ok = 7
Output: 2
Rationalization: The doable pairs are: (1, 2), (2, 3).
For i = 1, j = 2, Worth of the expression = 1 * 1 + 2 * 3 = 7.
For i = 2, j = 3, Worth of the expression = 1 * 3 + 2 * 2 = 7.

Enter: N = 2, arr[] = [1, 2], X =1, Y = 1, goal = 2
Output: 0
Rationalization: No pair fulfill the above situation.
For i = 1, j = 2, Worth of the expression = 1 * 1 + 1 * 2 = 3.

Naive Method: The fundamental thought to unravel the issue is as follows:

Discover all doable pairs of (i, j) and for every pair verify if (arr[i]*X + arr[j]*Y = Ok). In that case then increment the depend of pairs.

Comply with the beneath steps to implement the thought:

Initialize, an integer variable (say cnt as 0) to retailer the depend of the pairs.
Loop by the array from i = 0 to N – 2 :
- Loop for all of the second components from j = i + 1 to N-1:
  - Test if the sum of arr[i] * X and arr[j] * Y is the same as Ok.
  - Then increment the worth of cnt by 1.
Return the worth of cnt as the ultimate reply.

Beneath is the implementation of the above strategy.

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

int countPairs(int arr[], int n, int x,

int y, int okay)

{

int cnt = 0;

for (int i = 0; i < n - 1; ++i) {

for (int j = i + 1; j < n; ++j) {

int cur_sum = arr[i] * x

+ arr[j] * y;

if (cur_sum == okay) {

cnt++;

}

return cnt;

}

int essential()

{

int X = 4, Y = 2, Ok = 14;

int arr[] = { 3, 1, 2, 3 };

int N = sizeof(arr) / sizeof(arr[0]);

cout << countPairs(arr, N, X, Y, Ok);

return 0;

}

Time Complexity: O(N²)
Area Complexity: O(1)

Environment friendly Method: The issue might be solved effectively based mostly on the next mathematical remark:

arr[i]*X + arr[j]*Y = Ok
arr[i]*X = Ok – arr[j]*Y
So (Ok – arr[j]*Y) should be divisible by X and if arr[j] is discovered then the worth of arr[i] should be (Ok – arr[j]*Y)/X.

So to unravel the issue based mostly on the above remark, take into account every worth as arr[j] and attempt to discover the presence of arr[i] utilizing the above relation the place i is lower than j.

The above remark might be applied utilizing frequency counting. Comply with the beneath steps to unravel this drawback :

Initialize a variable (say cnt = 0) to retailer the depend of pairs.
Create a frequency array freq[] to retailer the frequency of the array components.
Loop by all the weather from j = 0 to N-1:
- Discover the worth of required arr[i] as proven within the above remark.
- If that aspect is current then improve the cnt by the frequency of that aspect.
- Improve the frequency of arr[j].
Return the worth of cnt as the ultimate reply.

Beneath is the implementation of the above strategy :

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

int countPairs(int arr[], int n, int x,

int y, int okay)

{

int cnt = 0;

unordered_map<int, int> freq;

for (int i = 0; i < n; ++i) {

int rhs = okay - arr[i] * y;

if (rhs % x || rhs <= 0) {

freq[arr[i]]++;

proceed;

}

rhs /= x;

cnt += freq[rhs];