CODEWITHSUNDEEP
java
AlexWhite
AlexWhite

Reputation: 143

Count of elements from the array

I am counting the element from array, which is greater then the given element (k)

   // Java implementation of the approach
class GFG
{
     
// Function to return the count of elements
// from the array which are greater than k
static int countGreater(int arr[], int n, int k) //arr-array, n-array length, k-number
{
//here first I sorted array
    int l = 0;
    int r = n - 1;
 
    // Stores the index of the left most element
    // from the array which is greater than k
    int leftGreater = n;
 
    // Finds number of elements greater than k
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        // If mid element is greater than
        // k update leftGreater and r
        if (arr[m] > k) {
            leftGreater = m;
            r = m - 1;
        }
 
        // If mid element is less than
        // or equal to k update l
        else
            l = m + 1;
    }
 
    // Return the count of elements greater than k
    return (n - leftGreater);
}

I solved with comparing only one number, but what if I have an array to compare with

Upvotes: 0

Views: 117

Answers (3)

Valery
Valery

Reputation: 315

There is a varying solutions. So, I can show you several.

First of all, you don't need properties that store the length of an array. You have to do that in C/C++, but not in Java.

Here are some solutions:

  1. A simple solution
private static int[] countGreater(int[] arr, int[] arr2) {
    int walkThroughArrayLength = arr2.length;
    int[] result = new int[walkThroughArrayLength];
    for (int i = 0; i < walkThroughArrayLength; i++) {
        int counter = 0;
        for (int a1 : arr) {
            if (a1 > arr2[i]) {
                counter++;
            }
        }
        result[i] = counter;
    }
    return result;
}
  1. Solution with Stream API
private static int[] countGreater(int[] arr, int[] arr2) {
    return Arrays.stream(arr2)
            .map(a2 ->
                    (int) Arrays.stream(arr)
                            .filter(a1 -> a1 > a2)
                            .count())
            .toArray();
}

Upvotes: 1

RaffleBuffle
RaffleBuffle

Reputation: 5455

A simple O(nk) solution would be to go through arr for each number in arr2 and count the number of values that are greater.

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k)
{       
    int[] res = new int[arr2.length];
    
    for(int i=0; i<k; i++)
    {
        int count = 0;
        for(int v : arr)
            if(v > arr2[i]) count++;
        res[i] = count;
    }
    
    return res;
}

However, we can do better than this by extending the method you've already identified - sorting arr and using binary search to identify the position of each value in arr2. If arr2 is also sorted then we can use the previously identified position as the initial left-hand edge of our binary search, since we know that subsequent elements in arr2 have to be greater than the current value.

Here's some Java code to illustrate:

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k)
{
    Collections.sort(Arrays.asList(arr));
    // assume arr2 is sorted, otherwise results could be out of order
    
    int[] res = new int[arr2.length];
    
    for(int i=0, pos=0; i<k; i++)
    {
        pos = 1 + Arrays.binarySearch(arr, pos, n, arr2[i]);
        if(pos < 0) pos = -pos;
        res[i] = n - pos;
    }
    
    return res;
}

I've simplified the code quite a bit by making use of the Arrays.binarySearch method.

For small values of n and k the simple approach will probably be faster, but as they grow the binarySearch approach will take over, despite the cost of the initial sort.

Upvotes: 0

Obinna Nnamani
Obinna Nnamani

Reputation: 31

This is easier when stream is used. You can simply do

public static long countGreater(int[] arr, int k) {

    IntStream stream = IntStream.of(arr);

    long count = stream.filter(number -> number > k).count();

    return count;
}

Upvotes: 0

Related Questions