Count of ways to choose an integer that has exactly K larger elements in Array

0 0 7 minutes read

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 5

Input: 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 k^th 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 integers
int 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 code
int 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 approach
import java.util.*;
 
class GFG
{
 
// Function to returns the 
// required count of integers
static 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 code
public 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 integers
def 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 code
arr = [ 100, 200, 400, 50 ]
k = 3
n = len(arr)
   
# Function Call
print(countWays(n, arr, k))
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# implementation of the approach
using 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 integers
function 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 code
var arr = [100, 200, 400, 50];
var k = 3;
var n = arr.length;
console.log(countWays(n, arr, k));
 
</script>

Output

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 K
int 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 count
 
arr = [1, 3, 4, 6, 8]
K = 2
print(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 K
function 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 function
var arr = [1, 3, 4, 6, 8];
var K = 2;
console.log(count_integer(arr, K));
 
// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL

Output

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 zambiatek!