Count the number of times a particular pair (x,y) appears in the array in O(N) time

Question

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 .

2)Adding code is optional .

3)Use Format option while adding code

 

The pair is valid only if x occurs before y

Answer 1

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=[0]*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

Comments

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.

---

Oh sorry I didn't read that constraint.
Let me edit my answer.

Answer 2

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[0] = 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