Efficient algorithm to find first available name

Posted by Avrahamshuk on Stack Overflow See other posts from Stack Overflow or by Avrahamshuk
Published on 2011-01-14T21:41:15Z Indexed on 2011/01/14 21:53 UTC
Read the original article Hit count: 369

I have an array containing names of items. I want to give the user the option to create items without specifying their name, so my program will have to supply a unique default name, like "Item 1".

The challenge is that the name has to be unique so i have to check all the array for that default name, and if there is an item with the same name i have to change the name to be "Item 2" and so on until i find an available name.

The obvious solution will be something like that:

String name;
for (int i = 0 , name = "Item " + i ; !isAvailable(name) ; i++);

My problem with that algorithm is that it runs at O(N^2).

I wonder if there is a known (or new) more efficient algorithm to solve this case.

In other words my question is this: Is there any algorithm that finds the first greater-than-zero number that dose NOT exist in a given array, and runs at less that N^2?

Thanks!

© Stack Overflow or respective owner

Related posts about arrays

Related posts about algorithm