Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

*Note: Even
though there really is nothing stopping you from finding a solution to
this on the internet, try to keep honest, and come up with your own
answer. It's all about the participation!*

Do you have code puzzlers that you'd like to share with the DZone community? If so, please submit here.

**Find the Missing Number in the Array **

Given a sorted array of numbers from 0 to n, with only one number missing in the sequence, write a method that will find that number.

Catch up on all our previous puzzlers here.

## Comments

## Ajinkya Vaze replied on Thu, 2013/02/28 - 8:28am

## Vijay Nathani replied on Thu, 2013/02/28 - 9:02am in response to: Ajinkya Vaze

This is a trick question.

Basically, the fastest way to do the same will be to use binary search. Instead of the algorithm being O(n), it will be O(log n) with base 2 for logarithm.

Groovy Solution

## Csaba Okrona replied on Thu, 2013/02/28 - 8:57am

## Régis Décamps replied on Thu, 2013/02/28 - 9:02am in response to: Vijay Nathani

Wait a minute... You need some indication during a binary search (you need to know whether the node you are looking for is smaller/bigger than the node you are currently looking at). You don't have this information when you are looking for a missing number.

Maybe you can explain a little more what you have in mind, because I'm probably missing something.

## Vijay Nathani replied on Thu, 2013/02/28 - 9:04am in response to: Régis Décamps

I added Groovy solution to my previous answer.

## Régis Décamps replied on Thu, 2013/02/28 - 9:10am in response to: Ajinkya Vaze

## Régis Décamps replied on Thu, 2013/02/28 - 9:15am in response to: Vijay Nathani

`assert missingNumber([0,2,3,4]) == 1`

You'll see your approach is wrong. I don't think one can beat O(n)## Vijay Nathani replied on Thu, 2013/02/28 - 10:09am in response to: Régis Décamps

There was a bug in my previous program. Instead of

it should be

But the logic is correct and peformance is O(log n). The corrected groovy program is

## Prasoon Kumar replied on Thu, 2013/02/28 - 11:02am

The following PHP program will do it in O(n) vs O(log(n)) suggested above.

Prasoon Kumar

## Earnest Dyke replied on Thu, 2013/02/28 - 12:58pm

## Ajinkya Vaze replied on Fri, 2013/03/01 - 3:04am in response to: Vijay Nathani

When we are doing binary search we need some key....what is the search key here?

## Vijay Nathani replied on Fri, 2013/03/01 - 3:40am in response to: Ajinkya Vaze

Array is sorted.

Read my groovy program.

## Remigio Di Muzio replied on Sat, 2013/03/02 - 3:07am in response to: Régis Décamps

## Ajinkya Vaze replied on Sat, 2013/03/02 - 6:02am in response to: Vijay Nathani

## Daniel Sobral replied on Wed, 2013/03/06 - 10:26am

Easy solution (not efficient) in Scala (btw, when will we get syntax highlighting for it?):

## Ian Herbert replied on Wed, 2013/03/06 - 1:06pm

## Sennen Ekouaghe replied on Wed, 2013/03/06 - 5:30pm

## Sennen Ekouaghe replied on Wed, 2013/03/06 - 5:52pm in response to: Sennen Ekouaghe

Tested on [m,n] intervals with m >= 0 for arrays composed with distinct numbers.

## Régis Décamps replied on Fri, 2013/03/08 - 6:36am in response to: Remigio Di Muzio

Yes, thanks for the explanation. The trick was to compare the number with its index indeed. It's pretty clear now.

## Abhilash Ponnachan replied on Sat, 2013/03/16 - 10:00am

Here is a Haskell hack :

let missing ns = last ns * (last ns + 1) / 2 - (sum ns)

## Bob Beechey replied on Sat, 2013/03/30 - 10:27pm

Python hack: