This is a good example of why programming puzzles do a poor job of testing an applicant's problem solving ability.<p>These programming puzzles are like the old fashion puzzles <a href="http://www.lehmans.com/store/Toys___Iron_Puzzles" rel="nofollow">http://www.lehmans.com/store/Toys___Iron_Puzzles</a>.<p>* If you know the "trick", they are trivial and don't test your skill at all.<p>* If you don't know the "trick", they are extremely frustrating and don't test your skill at all.<p>* Once you know the "trick", you will look like a "genius" every time.<p>* The "tricks" are widely available on the internet.<p>Besides the "trick" issue, the "integer not in four billion" suffers from having "domain knowledge bias", which is pretty common with programming puzzle problems. This is one of the reasons programmers only hire programmers like themselves - they cannot see outside their bias box.<p>For someone with a bit-twiddling C/assembly background, the obvious assumption behind the puzzle is that "four billion" and "integer not among" and 1GByte implies you are given the unsigned integers 0..2^32-1 with one of them missing and you are to make a bit-map of the integers.<p>For someone without a bit-twiddling C background, they quite likely will both produce a perfectly valid answer and will fail the interview. For instance, finding the highest value <i>n</i> and returning <i>n+1</i> is both <i>correct</i> and <i>better</i> than the implicitly "correct" answer in that it will take <i>much</i> less memory than the implicit algorithm and run much faster.<p>In fact, if you are allowed to take advantage of the puzzle author's bias box, the answer 2^32 will be correct every time and will be impossibly fast compared to the "correct" answer or even the <i>n+1</i> answer. In fact, the <i>n+1</i> answer will always be 2^32, given the bias box - the puzzle author cannot conceive of an integer larger than 2^32-1.
First, find total number of digits of the 3 999 999 999 smallest integers.<p>Let's assume 0 doesn't count. The first 9 numbers have 1 digit each. The next 90 numbers have 2 digits each. The next 900 have 3, etcetera. That's 38 888 888 889 digits. Assume one byte per digit. Add a delimiter between every two numbers, plus one delimiter between the 3 999 999 999th and 4 000 000 000th number. That gives us 42 888 888 888 bytes.<p>Subtract that number from the total file size to get the number of digits in the final number. Say the file is 40 GiB. 40 GiB is 42 949 672 960 bytes. That leaves 60 784 072 bytes (or digits) for the 4 000 000 000th number.<p>Add 1 to that number to make sure it's bigger than any of the numbers that can possibly be in the file. Now construct a number of 60 784 073 digits by whatever method you wish.