Counting pairs with condition in even Array halves
Given an array arr[] of integers of size n where n is even, the task is to calculate the number of pairs (i, j) such that i lies in the first half of the array 0 ≤ i < n/2 and j lies in the second half of the array
n/2 ≤ j < n and arr[i] ≥ 5*arr[j].
Note: 0-based indexing is used and n is even.
Examples:
Input: n = 4, arr = {10, 2, 2, 1}
Output: 2
Explanation: As we can see index i = 0 and j = 2 where arr[0] ≥ 5*arr[2] (10 ≥ 5*2)is fulfilled so this forms a pair and in same manner index i = 0 and j = 3 forms a pair. So total 2 such pairs exist.Input: n = 6, arr = {10, 8, 2, 1, 1, 2}
Output: 5
Explanation: As we can see index i = 0 and j = 3 where arr[0] ≥ 5*arr[3] (10 ≥ 5*1) is fulfilled so this forms a pair and in same manner (0, 4), (0, 5), (1, 3), (1, 4) also form a pair. So total 5 such pairs.
Approach: To solve the problem follow the below idea:
The idea is to sort the array’s first and second halves in ascending and descending order, respectively. This is due to the fact that we need to find pairs (i, j) where i should be less than j and arr[i] ≥ 5*arr[j].
Below are the steps for the above approach:
- Sort the first half of the array from index 0 to n/2 and then sort the second half of the array from index n/2 to n.
- Initialize a variable ans = 0 to store the count of the number of such pairs.
- Initialize a variable right = n/2.
- Initialize a variable left = 0 and run a loop and use this variable to iterate across the first half of the array.
- Run another loop to iterate the second half of the array and increment the value of right till right < n and arr[left] ≥ 5 * arr[right].
- Update the ans variable with the difference between right and n/2.
- Return the value of ans.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <iostream> #include <algorithm> using namespace std; int findPairs( int n, int arr[]) { // Sort the first half of the array sort(arr, arr + n / 2); // Sort the second half of the array sort(arr + n / 2, arr + n); int ans = 0; int right = n / 2; // Iterate over the first half of the array for ( int left = 0; left < n / 2; left++) { // Move the right pointer until the condition is satisfied while (right < n && arr[left] >= 5 * arr[right]) { right++; } // Add the number of valid pairs to the answer ans += right - n / 2; } return ans; } // Driver code int main() { int arr[] = {10, 2, 2, 1}; int n = sizeof (arr) / sizeof (arr[0]); // Call the function and print the result int result = findPairs(n, arr); cout << result << endl; return 0; } |
Java
// Java code for the above approach: import java.util.*; public class GFG { public static int findPairs( int n, int [] arr) { Arrays.sort(arr, 0 , n / 2 ); Arrays.sort(arr, n / 2 , n); int ans = 0 ; int right = n / 2 ; for ( int left = 0 ; left < n / 2 ; left++) { while (right < n && arr[left] >= 5 * arr[right]) { right++; } ans += right - n / 2 ; } return ans; } // Drivers code public static void main(String[] args) { int [] arr = { 10 , 2 , 2 , 1 }; int n = arr.length; int result = findPairs(n, arr); // Function Call System.out.println(result); } } |
Python3
def findPairs(n, arr): # Sort the first half of the array arr[:n / / 2 ] = sorted (arr[:n / / 2 ]) # Sort the second half of the array arr[n / / 2 :] = sorted (arr[n / / 2 :]) ans = 0 right = n / / 2 # Iterate over the first half of the array for left in range (n / / 2 ): # Move the right pointer until the condition is satisfied while right < n and arr[left] > = 5 * arr[right]: right + = 1 # Add the number of valid pairs to the answer ans + = right - n / / 2 return ans # Driver code arr = [ 10 , 2 , 2 , 1 ] n = len (arr) # Call the function and print the result result = findPairs(n, arr) print (result) |
C#
using System; using System.Linq; class Program { static int FindPairs( int n, int [] arr) { // Sort the first half of the array Array.Sort(arr, 0, n / 2); // Sort the second half of the array Array.Sort(arr, n / 2, n - n / 2); int ans = 0; int right = n / 2; // Iterate over the first half of the array for ( int left = 0; left < n / 2; left++) { // Move the right pointer until the condition is satisfied while (right < n && arr[left] >= 5 * arr[right]) { right++; } // Add the number of valid pairs to the answer ans += right - n / 2; } return ans; } static void Main( string [] args) { int [] arr = { 10, 2, 2, 1 }; int n = arr.Length; // Call the function and print the result int result = FindPairs(n, arr); Console.WriteLine(result); } } // This code is contributed by Prajwal Kandekar |
Javascript
function findPairs(n, arr) { // Sort the first half of the array arr.splice(0, Math.floor(n / 2), ...arr.slice(0, Math.floor(n / 2)).sort()); // Sort the second half of the array arr.splice(Math.floor(n / 2), n - Math.floor(n / 2), ...arr.slice(Math.floor(n / 2)).sort()); let ans = 0; let right = Math.floor(n / 2); // Iterate over the first half of the array for (let left = 0; left < Math.floor(n / 2); left++) { // Move the right pointer until the condition is satisfied while (right < n && arr[left] > 5 * arr[right]) { right++; } // Add the number of valid pairs to the answer ans += right - Math.floor(n / 2); } return ans; } // Driver code const arr = [10, 2, 2, 1]; const n = arr.length; // Call the function and print the result const result = findPairs(n, arr); console.log(result); |
2
Time Complexity: O(N * logN)
Auxiliary Space: O(1)