If I am wrong, please correct me. I think if you are using the ceiling as the gap value, you may not really using n-1 buckets. For example: [0, 1, 3, 4, 5, 7] , the gap will be ceil[(7-0)/(6-1)]=2, then our n-1 buckets will be 0, 1, 2, 3, 4, but the max number 7 actually will fall into bucket 3 (although we are not really put it into the bucket), so you are only using four buckets instead of five (the last bucket 4 is wasted). In that case, the assumption that we at least have one bucket empty is not correct.

Maximum Gap