An SQL Puzzle
by Jonathan Wellons
Suppose we have a table called 'Tree' with only one column called 'lemons' (unsigned int) for a very simple application to document the productivity of our trees. Typical data might be five rows with lemons numbering 0, 1, 2, 3 and 7. Of course, there can be any number of trees and the number of lemons can span the full range of an int.
The Puzzle
Write a pure SQL program that computes the smallest nonnegative integer, such that no tree has that number of lemons. In the typical data above, the answer would be 4. Just to standardize, your solution must run in MySQL 4.1.12.
Guidelines
 Obviously, you could chain an huge tower of subqueries together
select
if(
(select * from min_absent where value = 0 limit 1) is null, 0,
if(
(select * from min_absent where value = 1 limit 1) is null, 1,
if(
(select * from min_absent where value = 2 limit 1) is null, 2,
if(
(select * from min_absent where value = 3 limit 1) is null, 3,
if(
(select * from min_absent where value = 4 limit 1) is null, 4,
...
)
)
)
)
)
up to the full range of an int, but this is not elegant.  There are also tricks involving creating new (nontemporary) tables. This requires both more permissions, that there be no table name conflicts and it is less 'lightweight' and clean than selects. You don't need to do this, either.
Solution
To come in a few days if no one finds an answer.
8 Comments
Dan_Zambonini 20050824 01:41:16 
Haven't really tested it Off the top of my head, something like...

BamaSQL 20050824 13:26:51 
Solution? How about this:

BamaSQL 20050824 13:36:22 
Solution? Hmm. That won't work if the answer is really zero. Need to tinker it a bit. 
wellons 20050824 13:53:37 
Solution? That one has a good intuitive feel that parallels the phrasing in the problem, although Dan_Zambonini's solution was the one I had in mind. Unfortuately, both of these solutions miss some cases.

wellons 20050824 13:55:54 
Solution? Sorry, I guess I was writing my reply to your first post when you submitted this. 
APClarke 20050825 04:44:37 
Not familar with MySQL... ...so I'm posting a solution that uses Oracle's set operators. I don't know whether MySQL has such (although I presume so) or whetehr it has a row number function like Oracle's ROWNUM pseudocolumn.

BamaSQL 20050825 05:40:56 
Solution? An NVL on the first select would take care of case #2. 
awfief 20051220 13:19:05 
use derived tables. . . set @lemons_prev:=0
