0 like 0 dislike
483 views
Expected Time Complexity : O(N) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 300 10000 5 5 200

(x,y) = (100,200)

Output : There are two pairs (100,200) and (100,200) in the array , hence answer is '2' .

Note :

1)Algorithm-explanation is must .

3)Use Format option while adding code

The pair is valid only if x occurs before y
| 483 views

1 like 0 dislike

Approach:-

Step1- Count the no. of occurances of y after an index i. We have to do this for each index so it can be done with the help of a single loop and O(N) time complexity and let the result be stored in an temporary array let say temp.

Step2- Initialise your ways to 0. And run a loop from starting to end of the array. Now whenever we find x we see that how many occurances of y are there the current index. This can be done in O(1) time as we have already stored their count in temp. And this point we will add temp[i] to ways.

Step3- Now just return the ways.

Explanation:-

After counting the no. of occurances of y after all indices in array, to form an ordered pair of (x, y)  we have to choose a x from array and see how many y are occuring after this index. So the total no. of ways in which this pair can be formed with x aa current element will be temp[i] because we have to choose any one of these as y.

Code:-

```def findNoOfPairs(arr,n,x,y):
temp=*n
y=0
for i in range(n-1,-1,-1):
temp[i]=y
if arr[i]==y:
y+=1
ways=0
for i in range(n):
if arr[i]==x:
ways+=temp[i]
return ways```
by (460 points)
selected
0 0
Hello, your approach fails for some cases where x does not occur before y.
Example case : 1 2 3 4 5
Pair(x,y) is  (2,1)  .
Here the output shoukd be zero.
0 0
Oh sorry I didn't read that constraint.
1 like 0 dislike

Approach :

As the order of (x,y) matters (means y should always occur after x )

First Lets Create an array 'arr' which is used to store the occurrence of y from index 'i' .

Initially, all values in arr are zero.   if(a[n-1]==y) update arr[n-1] as 1 .

Now iterate the given array 'a' in reverse order from n-1 to 0 .

if current element is equal to y just update arr[i] as arr[i+1]+1 .

else copy the arr[i+1] into arr[i]

for example if given array is { 1, 2 , 3 , 2 , 4, 2} and (x,y) as (1,2)

then arr looks like { 3, 3, 3,2, 1, 1}   (every element indicates the no of times y occurred from that position towards the right  here arr = 3 means y(i.e 2) occurred 3 times from 0th position  )

after getting the above-mentioned array 'arr'.

we can start calculating the answer

count =0 (answer to be printed)

just do the following process :

iterate the original array from left to right  i.e from 0 to n-2;

and check if current element is equal to 'x' if it is just increment the ans with arr[i+1]   (arr[i+1] indicates no of times 'y' occured from that position  )

Finally output the count

```Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n=7;
vector<int> a={100,200,300,10000,5,5,200};
int x,y;
x=100,y=200;
vector<int> arr(n);
if(a[n-1]==y) arr[n-1]=1;
for(int i=n-2;i>=0;i--)
{
if(a[i]==y)
arr[i]=arr[i+1]+1;
else arr[i]=arr[i+1];
}
int count=0;
for(int i=0;i<n-1;i++)
{
if(a[i]==x)
{
count+=arr[i+1];
}
}
cout<<count<<endl;
return 0;
}
```

Input 1  : {100,200,300,10000,5,5,200} (x,y)= (100,200)

output 1: 2

input 2 :{ 1, 2 , 2 , 1  ,2  , 2 , 3}  (x,y)=(1,2)

output 2 : 6

by Expert (540 points)