Given an array A[] of N integers, the duty is to search out the variety of pairs of indices (1 ≤ i, j ≤ N) within the array such that A[i] < i < A[j] < j.
Examples:
Enter: N = 8, A[] = {1, 1, 2, 3, 8, 2, 1, 4}
Output: 3
Rationalization: The pairs satisfying the given situation are {(2, 4), (2, 8), (3, 8)}.
For the pair (2, 4): A[2] = 1(1-based indexing), A[4] = 3 and 1 < 2 < 3 < 4.
For the pair (2, 8): A[2] = 1, A[8] = 4 and 1 < 2 < 4 < 8.
For the pair (3, 8): A[3] = 2, A[8] = 4 and a pair of < 3 < 4 < 8.Enter: N = 2, A[] = {1, 2}
Output: 0
Naive Method: A fundamental option to clear up the issue can be to traverse the array utilizing two nested loops and verify the situation for every potential pair.
Time Complexity: O(N2)
Auxiliary House: O(1)
Environment friendly Method: The issue could be solved utilizing a grasping strategy and binary search.
Given Situation is A[i] < i < A[j] < j. Lets break it into three separate circumstances:
The weather of array having A[i] ≥ i cannot fulfill the first and third situation and therefore won’t be the a part of any pair satisfying the given situation. For remainder of the weather (say legitimate components) 1st and third circumstances are already glad. So, among the many legitimate components, merely rely the variety of pairs (i, j) satisfying the 2nd situation i.e. i < A[j].
Comply with the steps to unravel the issue:
- Initialize a variable (say ans) with 0, to retailer the overall variety of pairs and a vector (say v) to retailer the positions of legitimate components.
- Whereas iterating by the array, if a component is larger than or equal to its place, then skip the iteration, as that factor would by no means be capable of type a pair satisfying the required circumstances.
- Else, simply add the variety of positions lower than the present factor to the reply (to fulfill the 2nd situation i < A[j]), which could be calculated by the decrease sure on vector v of positions.
- Additionally, at finish of every iteration, insert the place of every legitimate factor to the vector v.
Under is the implementation for the above strategy:
C++
|
|
Time Complexity: O(N * log(N))
Auxiliary House: O(N)
