Count pairs in a sorted array whose sum is less than x - GeeksforGeeks
Given a sorted integer array and number x, the task is to count pairs in array whose sum is less than x.
http://www.geeksforgeeks.org/count-pairs-difference-equal-k/
http://www.geeksforgeeks.org/count-pairs-with-given-sum/
Read full article from Count pairs in a sorted array whose sum is less than x - GeeksforGeeks
Given a sorted integer array and number x, the task is to count pairs in array whose sum is less than x.
int countPairsWithDiffK(int arr[], int n, int k){ int count = 0; // Initialize count // Initialize empty hashmap. bool hashmap[MAX] = {false}; // Insert array elements to hashmap for (int i = 0; i < n; i++) hashmap[arr[i]] = true; for (int i = 0; i < n; i++) { int x = arr[i]; if (x - k >= 0 && hashmap[x - k]) count++; if (x + k < MAX && hashmap[x + k]) count++; hashmap[x] = false; } return count;}int countPairsWithDiffK(int arr[], int n, int k){ int count = 0; sort(arr, arr+n); // Sort array elements int l = 0; int r = 0; while(r < n) { if(arr[r] - arr[l] == k) { count++; l++; r++; } else if(arr[r] - arr[l] > k) l++; else // arr[r] - arr[l] < sum r++; } return count;}int findPairs(int arr[],int n,int x){ int l = 0, r = n-1; int result = 0; while (l < r) { // If current left and current // right have sum smaller than x, // the all elements from l+1 to r // form a pair with current l. if (arr[l] + arr[r] < x) { result += (r - l); l++; } // Move to smaller value else r--; } return result;}
Given an integer array and a positive integer k, count all distinct pairs with difference equal to k.
int binarySearch(int arr[], int low, int high, int x){ if (high >= low) { int mid = low + (high - low)/2; if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, (mid + 1), high, x); else return binarySearch(arr, low, (mid -1), x); } return -1;}/* Returns count of pairs with difference k in arr[] of size n. */int countPairsWithDiffK(int arr[], int n, int k){ int count = 0, i; sort(arr, arr+n); // Sort array elements /* code to remove duplicates from arr[] */ // Pick a first element point for (i = 0; i < n-1; i++) if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1) count++; return count;}
Given an array of integers, and a number ‘sum’, find the number of pairs of integers in the array whose sum is equal to ‘sum’.
int getPairsCount(int arr[], int n, int sum){ unordered_map<int, int> m; // Store counts of all elements in map m for (int i=0; i<n; i++) m[arr[i]]++; int twice_count = 0; // iterate through each element and increment the // count (Notice that every pair is counted twice) for (int i=0; i<n; i++) { twice_count += m[sum-arr[i]]; // if (arr[i], arr[i]) pair satisfies the condition, // then we need to ensure that the count is // decreased by one such that the (arr[i], arr[i]) // pair is not considered if (sum-arr[i] == arr[i]) twice_count--; } // return the half of twice_count return twice_count/2;}Read full article from Count pairs in a sorted array whose sum is less than x - GeeksforGeeks
