Posts Noble Integer
Post
Cancel

Noble Integer

Problem Description

Given an integer array A, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p.

Solution

Let’s say we sort the array in ascending order and iterate from the right.

Important Observations:

  • If A[i] == A[i+1], the number of elements which are greater than them will be the same.
  • If A[i] != A[i+1], the number of elements which are greater than A[i] will be equal to (n-i-1) since we have sorted the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {

    public int solve(ArrayList<Integer> A) {

        Collections.sort(A);

        int n = A.size();

        if(A.get(n-1) == 0) return 1; //Edge case, if the last element is 0

        for(int i=0; i<n-1; i++){

            int p = A.get(i);
            int right = n-i-1;

            //current element == number of elements on its right
            //The list can also have duplicates. If the number of its right is a duplicate, we cannot include that since we are looking for stricly greater
            if(p == right && p != A.get(i+1)) return 1;
        }

        return -1;

    }
}

ANOTHER WAY TO CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {

    public int solve(ArrayList<Integer> A) {

        //sort in ascending order
        Collections.sort(A);

        int n = A.size();

        //iterate from left to right
        for(int i=0; i<n; i++){

            //This is the main part:
            //If there were no duplicates, we could have said that all numbers towards right are greater
            //But, if there are any duplicates, we cannot do that. We also don't know how many duplicates can be there.
            //But it is safe to skip the duplicates except the last one.
            //For the last element in the continous sequence of duplicates, we can definitely say that all elements towards its right are greater
            //If that matches the value of that number, we have a nobel number
            //Example: [0, 0, 1, 2, 3, 3, 6, 7, 9]
            //For all occurances of 3, the number of elements more than 3 is going to be the same, which is 3
            //We know we would need to ignore the duplicates when considering the first 3. But we don't know how many duplicates will be there.
            //So, we can simply calculate the answer for the last occurance of 3. The answer will be the same for all occurances of 3!
            if(i < n-1 && A.get(i+1) == A.get(i)) continue;

            int x = A.get(i);
            int y = n - i - 1;

            if(x == y)
                return 1;

        }


        return -1;

    }

}
This post is licensed under CC BY 4.0 by the author.