Given an array arr[] of N distinct integers and a positive integer K, the task is to find the number of ways of choosing an integer X such that there are exactly K elements in the array that are greater than X.
Examples:
Input: arr[] = {1, 3, 4, 6, 8}, K = 2
Output: 3
Explanation: X can be chosen as 4 or 5Input: arr[] = {1, 2, 3}, K = 1
Output: 2
Explanation: No matter what integer you choose as X, it’ll never have exactly 2 elements greater than it in the given array.
Approach:
Count total number of distinct elements in the array. If the count of distinct elements is less than or equal to k, then 0 ways are possible, Else the total possible ways will be equal to 1 + the difference between (k+1)th largest element and kth largest element .
Follow the below steps to Implement the approach:
- If n is less than k return 0
- Else sort the array in increasing order and return the value arr[n-k] – arr[n-k-1] + 1.
Below is the Implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to returns the required count of integersint countWays(int n, vector<int>v, int k){ if (n <= k) return 0; sort(v.begin(),v.end()); return v[n-k]-v[n-k-1]+1; // Return the required count}// Driver codeint main(){ vector<int>arr = { 100, 200, 400, 50 }; int k = 3; int n = arr.size(); //Function Call cout << countWays(n, arr, k);} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to returns the // required count of integersstatic int countWays(int n, int arr[], int k){ if (n <= k) return 0; Arrays.sort(arr); // Return the required count return arr[n-k]-arr[n-k-1]+1;}// Driver codepublic static void main(String args[]){ int arr[] = { 100, 200, 400, 50 }; int k = 3; int n = arr.length; System.out.println(countWays(n, arr, k));}}// This code id contributed by// Surendra_Gangwar |
Python
# Python implementation of the approach# Function to returns the required count of integersdef countWays(n, v, k): if (n <= k): return 0 v.sort() # Return the required count return v[n - k] - v[n - k - 1] + 1# Driver codearr = [ 100, 200, 400, 50 ]k = 3n = len(arr) # Function Callprint(countWays(n, arr, k))# This code is contributed by Samim Hossain Mondal. |
C#
// C# implementation of the approachusing System;class GFG { // Function to returns the // required count of integers static int countWays(int n, int[] arr, int k) { if (n <= k) return 0; Array.Sort(arr); // Return the required count return arr[n - k] - arr[n - k - 1] + 1; } // Driver code public static void Main() { int[] arr = { 100, 200, 400, 50 }; int k = 3; int n = arr.Length; Console.Write(countWays(n, arr, k)); }}// This code is contributed by// Samim Hossain Mondal. |
Javascript
<script>// JavaScript implementation of the approach// Function to returns the required count of integersfunction countWays(n, arr, k){ if (n <= k) { return 0; } arr.sort(function(a, b) {return a - b;}); // Return the required count return arr[n - k] - arr[n - k - 1] + 1;}// Driver codevar arr = [100, 200, 400, 50];var k = 3;var n = arr.length;console.log(countWays(n, arr, k));</script> |
Output
51
Complexity Analysis:
- Time Complexity: O(N * log(N)), For sorting the array
- Auxiliary Space: O(1)
METHOD 2:Binary Search
APPRAOCH:
We can sort the input array and then for each element in the array, use binary search to find the number of elements that are larger by K.
ALGORITHM:
1.Sort the input array in non-decreasing order.
2.Initialize a count variable to 0.
3.For each element arr[i] in the array:
a. Set low = i + 1 and high = n – 1.
b. While low <= high:
i. Calculate the mid index using mid = (low + high) // 2.
ii. If arr[mid] – arr[i] == K, increment the count variable and break out of the loop.
iii. If arr[mid] – arr[i] > K, set high = mid – 1.
iv. If arr[mid] – arr[i] < K, set low = mid + 1.
4.Return the count variable.
C++
#include <iostream>#include <algorithm>#include <vector>// Function to count pairs of integers in an array that differ by exactly Kint count_integer(std::vector<int> arr, int K) { // Sort the array in ascending order std::sort(arr.begin(), arr.end()); // Get the length of the array int n = arr.size(); // Initialize a count variable to keep track of the number of pairs int count = 0; // Loop through each element of the array for (int i = 0; i < n; i++) { // Initialize the low and high pointers for binary search int low = i+1; int high = n-1; // Perform binary search to find the element that differs from the current element by K while (low <= high) { int mid = (low+high)/2; if (arr[mid] - arr[i] == K) { count++; break; } else if (arr[mid] - arr[i] > K) { high = mid-1; } else { low = mid+1; } } } // Return the count of pairs return count;}int main() { // Test the function std::vector<int> arr = {1, 3, 4, 6, 8}; int K = 2; std::cout << count_integer(arr, K) << std::endl; return 0;} |
Java
import java.util.Arrays;public class Main { // Function to count pairs of integers in an array // that differ by exactly K public static int count_integer(int[] arr, int K) { // Sort the array in ascending order Arrays.sort(arr); // Get the length of the array int n = arr.length; // Initialize a count variable to keep track of the number of pairs int count = 0; // Loop through each element of the array for (int i = 0; i < n; i++) { // Initialize the low and high pointers for binary search int low = i+1; int high = n-1; // Perform binary search to find the element that differs from the current element by K while (low <= high) { int mid = (low+high)/2; if (arr[mid] - arr[i] == K) { count++; break; } else if (arr[mid] - arr[i] > K) { high = mid-1; } else { low = mid+1; } } } // Return the count of pairs return count; } public static void main(String[] args) { // Test the function int[] arr = {1, 3, 4, 6, 8}; int K = 2; System.out.println(count_integer(arr, K)); }} |
Python3
def count_integer(arr, K): arr.sort() n = len(arr) count = 0 for i in range(n): low = i+1 high = n-1 while low <= high: mid = (low+high)//2 if arr[mid] - arr[i] == K: count += 1 break elif arr[mid] - arr[i] > K: high = mid-1 else: low = mid+1 return countarr = [1, 3, 4, 6, 8]K = 2print(count_integer(arr, K)) |
C#
using System;public class Program{ // Function to count pairs of integers in an array // that differ by exactly K public static int count_integer(int[] arr, int K) { // Sort the array in ascending order Array.Sort(arr); // Get the length of the array int n = arr.Length; // Initialize a count variable to keep track of the number of pairs int count = 0; // Loop through each element of the array for (int i = 0; i < n; i++) { // Initialize the low and high pointers for binary search int low = i + 1; int high = n - 1; // Perform binary search to find the element that differs from the current element by K while (low <= high) { int mid = (low + high) / 2; if (arr[mid] - arr[i] == K) { count++; break; } else if (arr[mid] - arr[i] > K) { high = mid - 1; } else { low = mid + 1; } } } // Return the count of pairs return count; } public static void Main(string[] args) { // Test the function int[] arr = { 1, 3, 4, 6, 8 }; int K = 2; Console.WriteLine(count_integer(arr, K)); }}// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
Javascript
// Function to count pairs of integers in an // array that differ by exactly Kfunction count_integer(arr, K) { // Sort the array in ascending order arr.sort(function(a, b) { return a - b; }); // Get the length of the array var n = arr.length; // Initialize a count variable to keep track of the // number of pairs var count = 0; // Loop through each element of the array for (var i = 0; i < n; i++) { // Initialize the low and high pointers for binary search var low = i + 1; var high = n - 1; // Perform binary search to find the element that // differs from the current element by K while (low <= high) { var mid = Math.floor((low + high) / 2); if (arr[mid] - arr[i] == K) { count++; break; } else if (arr[mid] - arr[i] > K) { high = mid - 1; } else { low = mid + 1; } } } // Return the count of pairs return count;}// Test the functionvar arr = [1, 3, 4, 6, 8];var K = 2;console.log(count_integer(arr, K));// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
Output
3
The time complexity of this approach is O(nlog(n))
The auxiliary space of this approach is 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!
