Hello Everyone,
Given N numbers and Q queries, every query consists of L and R, task is to find the number of such integers i (L<=i<R) such that Ai=Ai+1. Consider 0-based indexing.
Examples :
Input : A = [1, 2, 2, 2, 3, 3, 4, 4, 4]
Q = 2
L = 1 R = 8
L = 0 R = 4
Output : 5
2
Explanation: We have 5 index i which has
Ai=Ai+1 in range [1, 8). We have
2 indexes i which have Ai=Ai+1
in range [0, 4).
Input :A = [3, 3, 4, 4]
Q = 2
L = 0 R = 3
L = 2 R = 3
Output : 2
1
A naive approach is to traverse from L to R (Exclusive R) and count the number of index i which satisfies the condition Ai=Ai+1 for every query separately.
Below is the implementation of the naive approach :
// CPP program to count the number of indexes
// in range L R such that Ai = Ai+1
#include <bits/stdc++.h>
using namespace std;
// function that answers every query in O(r-l)
int answer_query( int a[], int n, int l, int r)
{
// traverse from l to r and count
// the required indexes
int count = 0;
for ( int i = l; i < r; i++)
if (a[i] == a[i + 1])
count += 1;
return count;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 2, 2, 3, 3, 4, 4, 4 };
int n = sizeof (a) / sizeof (a[0]);
// 1-st query
int L, R;
L = 1;
R = 8;
cout << answer_query(a, n, L, R) << endl;
// 2nd query
L = 0;
R = 4;
cout << answer_query(a, n, L, R) << endl;
return 0;
}
Output:
5 2
Time Complexity : O(R – L) for every query
Efficient approach: We can answer queries in O(1) time. The idea is to precompute a prefix array prefixans such that prefixans[i] stores the total count of the index from 0 to i that obeys the given condition. prefixans[R-1]-prefix[L-1] returns the total count of an index in the range [L, r) for every query.
Below is the implementation of the efficient approach :
// CPP program to count the number of indexes
// in range L R such that Ai=Ai+1
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
// array to store count of index from 0 to
// i that obey condition
int prefixans[N];
// precomputing prefixans[] array
int countIndex( int a[], int n)
{
// traverse to compute the prefixans[] array
for ( int i = 0; i < n; i++) {
if (a[i] == a[i + 1])
prefixans[i] = 1;
if (i != 0)
prefixans[i] += prefixans[i - 1];
}
}
// function that answers every query in O(1)
int answer_query( int l, int r)
{
if (l == 0)
return prefixans[r - 1];
else
return prefixans[r - 1] - prefixans[l - 1];
}
// Driver Code
int main()
{
int a[] = { 1, 2, 2, 2, 3, 3, 4, 4, 4 };
int n = sizeof (a) / sizeof (a[0]);
// pre-computation
countIndex(a, n);
int L, R;
// 1-st query
L = 1;
R = 8;
cout << answer_query(L, R) << endl;
// 2nd query
L = 0;
R = 4;
cout << answer_query(L, R) << endl;
return 0;
}
Output:
5 2
Time Complexity: O(1) for every query and O(n) for pre-computing.