Introduction
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 non-negative 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 (non-temporary) 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.
Haven't really tested it
Off the top of my head, something like...
SELECT min(current.lemons + 1) FROM Trees AS current LEFT JOIN Trees AS next ON (next.lemons = current.lemons + 1) WHERE next.lemons IS NULL;Might do it.
Solution?
How about this:
select min(lemons)+1
from tree
where ( (lemons+1)
not in
(select lemons from tree)
);
Solution?
Hmm. That won't work if the answer is really zero. Need to tinker it a bit.
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.
I'm really hoping that someone comes up with an elegant way to capture all situations including 1) where there isn't a tree with zero lemons and 2) where there are no trees. In both cases the answer is zero, and the most elegant approach to special cases is often make them not be special at all, perhaps by taking a more Mathematical stance. I don't know how to do this yet, and my "solution" is just Dan_Zambonini's select statement combined with some if clauses to detect scenarios 1 and 2.
Solution?
Sorry, I guess I was writing my reply to your first post when you submitted this.
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 pseudo-column.
This solution catches both special cases mentioned previously.
Cheers, APC
Solution?
An NVL on the first select would take care of case #2.
use derived tables. . .
set @lemons_prev:=0
set @lemons_now:=-1
select @lemons_prev+1 as answer from (select @lemons_prev:=@lemons_now as st,@lemons_now:=lemons as lemons,lemons-@lemons_prev as diff from (select lemons from Tree order by lemons) as dt1) as dt2 where diff>1 limit 1;