Skip to main content

Arrays Hands-On: Warming Up

Traversals - 3

Let me begin with a boring backstory.

I remember that when I was in the first semester, I was trying to get into a few coding societies in my college. I learned about this senior who had just gotten into Amazon, and he picked some juniors to whom he taught coding, and off I ran to give the entrance test for that.

Now, a problem very similar to this problem was one of the problems asked in the interview. It was mentioned that even if you don't know coding, try to write the logic that you would've used to find the answer, and I was clueless xD

Missing Number

In this problem, we'll be given an array of size N containing distinct numbers in the range 0 to N. In the given array, all the numbers will be present exactly once, but one of the numbers from the given range will be missing. Our target is to find the missing one.

How to solve it?

Let's just read the problem and try to think of any solution that comes to mind, without worrying about the time complexity for now.

Thinking out loud We know that the answer lies between 0 and N, right? So, what if we just try to check for each and every number in the range, whether it's present in the array or not?
Putting it together (the brute force solution) We'll iterate from num = 0 to N and do the following for each num:
  • Initialise a variable found with false.
  • Iterate over the elements of the array.
  • Change the value of found to true if num is found, and break.
  • If the value of found is false finally, it means we've found our culprit; otherwise keep going.
Implementing the above 
int missingNumber(vector<int>& nums) {
    int N = nums.size();
    for(int num = 0; num <= N; ++num) {
        bool found = false;
        for(int val : nums) {
            if(val == num) {
                found = true;
                break;
            }
        }
        if(found == false)
            return num;
    }
    return 0;
}
Time & Space Complexity (guess before opening)

If you're having difficulty in finding out the time & space complexity of the above code, I urge you to go back to that section and kindly read the articles again.

After reading them thoroughly, it should be fairly easy to understand that:

  • Time Complexity = O(N2)
  • Space Complexity = O(1)

How to solve it more efficiently?

Can we try to do it in O(N)? Come on, think about it before moving further. Spend at least 10 minutes.

Hint 1 Come on, try for 5 more minutes, then move forward.
Hint 2 The difference is only of 1 number. If that 1 number was also present in the array, then the array would've contained all of the 1st N natural numbers exactly once, and of course, 0 as well.

Rings any bells?

Hint 3

Can we try to do some math by only traversing the array once? And then compare the resultant with what the resultant would've been if that math was done on the 1st N natural numbers instead of the array elements?

Hint 4

Something around the sum of the array elements, may be?

Before you move on to the solution, just remember that once you read it, you can't take it back, so try to resist that urge and apply some mind to get to it yourself.

The Solution

Okay, so what we know is that the sum of 1st N natural numbers (and 0) is equal to N*(N+1)/2, correct?

This means that the sum of all the elements of the array will be equal to N*(N+1)/2 - our_ans because all the numbers from 1 to N are present in the array exactly once, except our_ans which is missing.

So, our_ans = N*(N+1)/2 - array_sum.

Let's implement now 
int missingNumber(vector<int>& nums) {
    int N = nums.size();
    int expected_sum = N*(N+1)/2, actual_sum = 0;

    for(int num : nums)
        actual_sum += num;

    return expected_sum - actual_sum;
}
Time and space Complexity
  • Time Complexity = O(N)
  • Space Complexity = O(1)

That's it for this article. I'd like to point out that there are more ways as well to solve it; you're welcome to try to think of more ways.

For those who might be interested, the question I faced in the entrance test was that all of the numbers in the range [1, N] will be present exactly once in the array, except one number, which will be present twice. So, the target was to find that odd one out.