Find the Noble Integer

Teiva Harsanyi

Published in

solvingalgo

2 min readSep 23, 2018

Problem

Noble Integer: InterviewBit

Given an integer array, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p.If such an integer is found return 1 else return -1.

Category: Arrays

Solving Process

Simplify Input

This problem is not very difficult but to solve it we have to apply a well known technique to simplify the given inputs.

Let’s take a small example:

2, 6, 1, 3

This input should return 1 as 2 is a noble integer. We know that by counting the number of integers greater than 2 (3 and 4).

Yet, how to solve this problem without having an implementation in O(n²)? The answer is to simplify the inputs.

What if in our case the array was sorted?

1, 2, 3, 6

The integer 2 is at index 1, whereas the array size is 4. The success condition is the following:

size(array) - index - 1 == array[i]

Once the problem is solved using a simplification, we need to check the implications in terms of complexity. If our solution is acceptable, we generalize to the initial problem.

In our case, we have to:

Sort the array => O(n log(n))
Iterate over each element and check the previous condition => O(n)

It means the solution is O(n log(n)).

Bear in mind, sorting an array can’t be done with a better solution than a O(n log(n)) (like a merge sort for example).

Also, we have to make sure our solution covers all corner cases.

What about the following example, after being sorted:

1, 2, 2, 3
   x

At index 1, the condition is going to be true. Yet, this should not be a match.

In our case, we also have to cover duplicate by checking if the next integer is equals to the current one.

A possible implementation in Java:

Find the Noble Integer

Problem

Solving Process

Simplify Input

Further reading

Written by Teiva Harsanyi