Given an array arr[] of integers of size n where n is even, the task is to calculate the number of pairs (i, j), where a pair is counted if
( 0 ≤ i < n/2, n/2 ≤ j < n, arr[i] ≥ 5*arr[j] ) these relations are fulfilled.
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 the same manner index i = 0 and j = 3 form a pair. So a total of 2 dominant pairs.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 dominant pair and in the same manner (0, 4), (0, 5), (1, 3), (1, 4) also form dominant pair.So a total of 5 dominant pairs.
Approach: To solve the problem follow the below idea:
This problem can be solved using Sorting and Lower Bound.
- Sort both halves separately.
- Now for each element of 2nd half just find lower_bound for 5*A[j] and add the number of elements greater or equal to 5*A[j] which is n/2-lower_bound_index.
- Return the ans.
Below is the implementation of the above approach:
C++
// C++ Implementation#include <bits/stdc++.h>using namespace std;// Function to count number of pairs// in given arrayint countPairs(int n, vector<int>& arr){ sort(arr.begin(), arr.begin() + n / 2); sort(arr.begin() + n / 2, arr.end()); int ans = 0; for (int i = n / 2; i < n; i++) { int ind = lower_bound(arr.begin(), arr.begin() + n / 2, 5 * arr[i]) - arr.begin(); ans += n / 2 - ind; } return ans;}// Driver codeint main(){ int n = 4; vector<int> arr = { 10, 2, 2, 1 }; // Function call cout << countPairs(n, arr) << endl; return 0;} |
Java
import java.util.Arrays;import java.util.List;import java.util.ArrayList;class GFG { // Function to count number of pairs in given array static int countPairs(int n, List<Integer> arr) { arr.subList(0, n / 2).sort(null); arr.subList(n / 2, n).sort(null); int ans = 0; for (int i = n / 2; i < n; i++) { int ind = lowerBound(arr.subList(0, n / 2), 5 * arr.get(i)); ans += n / 2 - ind; } return ans; } // Lower bound implementation for Java List static int lowerBound(List<Integer> list, int target) { int left = 0; int right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) < target) { left = mid + 1; } else { right = mid; } } return left; } // Driver code public static void main(String[] args) { int n = 4; List<Integer> arr = new ArrayList<>(Arrays.asList(10, 2, 2, 1)); // Function call System.out.println(countPairs(n, arr)); }}// Code was contributed by codearcade |
Python3
# Python3 Implementationimport bisect# Function to count number of pairs# in given arraydef countPairs(n, arr): arr[:n//2] = sorted(arr[:n//2]) arr[n//2:] = sorted(arr[n//2:]) ans = 0 for i in range(n//2, n): ind = bisect.bisect_left(arr[:n//2], 5 * arr[i]) ans += n // 2 - ind return ans# Driver codeif __name__ == '__main__': n = 4 arr = [10, 2, 2, 1] # Function call print(countPairs(n, arr)) |
C#
using System;using System.Collections.Generic;class MainClass { // Function to count the number of pairs in the given array static int CountPairs(int n, List<int> arr) { // Create sublists for the first and second halves List<int> firstHalf = arr.GetRange(0, n / 2); List<int> secondHalf = arr.GetRange(n / 2, n - n / 2); // Sort the sublists firstHalf.Sort(); secondHalf.Sort(); int ans = 0; for (int i = n / 2; i < n; i++) { // Find the index using lower_bound in the first half where // arr[i] * 5 is greater or equal int ind = LowerBound(firstHalf, arr[i] * 5); ans += n / 2 - ind; } return ans; } // Function to find the lower bound index in a sorted list static int LowerBound(List<int> list, int target) { int left = 0; int right = list.Count; while (left < right) { int mid = left + (right - left) / 2; if (list[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } public static void Main(string[] args) { int n = 4; List<int> arr = new List<int> { 10, 2, 2, 1 }; // Function call int result = CountPairs(n, arr); Console.WriteLine(result); }} |
Javascript
// Function to count number of pairs// in given arrayfunction countPairs(n, arr) { // Sorting array arr.splice(0, n/2, ...arr.slice(0, Math.floor(n / 2)).sort((a, b) => a - b)); arr.splice(n/2, n/2, ...arr.slice(Math.floor(n / 2)).sort((a, b) => a - b)); let ans = 0; // Iterating over second half // Add the number of elements greater or equal to 5*A[j] which is n/2 - lower_bound index for (let i = Math.floor(n / 2); i < n; i++) { let ind = arr.slice(0, Math.floor(n / 2)).findIndex((element) => element >= 5 * arr[i]); ans += Math.floor(n / 2) - ind; } return ans;}let n = 4;let arr = [10, 2, 2, 1];console.log(countPairs(n, arr)); |
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
