Generate an integer that is not among four billion given ones

by

Assuming that “integer” means 32 bits: 10 MB of space is more than enough for you to count how many numbers there are in the input file with any given 16-bit prefix, for all possible 16-bit prefixes in one pass through the input file. At least one of the buckets will have be hit less than 216 times. Do a second pass to find of which of the possible numbers in that bucket are used already.

If it means more than 32 bits, but still of bounded size: Do as above, ignoring all input numbers that happen to fall outside the (signed or unsigned; your choice) 32-bit range.

If “integer” means mathematical integer: Read through the input once and keep track of the largest number length of the longest number you’ve ever seen. When you’re done, output the maximum plus one a random number that has one more digit. (One of the numbers in the file may be a bignum that takes more than 10 MB to represent exactly, but if the input is a file, then you can at least represent the length of anything that fits in it).

More Related Contents:

  1. What should be the algorithm of the below statement?
  2. Finding all possible combinations of numbers to reach a given sum
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Nearest neighbors in high-dimensional data?
  5. Backtracking in A star
  6. how to calculate binary search complexity
  7. Binary Search in Array
  8. Algorithm to find multiple string matches
  9. Algorithm to find two repeated numbers in an array, without sorting
  10. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  11. O(klogk) time algorithm to find kth smallest element from a binary heap
  12. Print the biggest K elements in a given heap in O(K*log(K))?
  13. Find local minimum in n x n matrix in O(n) time
  14. Breadth First Search and Depth First Search
  15. What is the difference between Linear search and Binary search?
  16. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  17. How to determine if a point is in a 2D triangle? [closed]
  18. Data structures for loaded dice?
  19. Writing your own square root function
  20. Merge Sort a Linked List
  21. How do you like your primary keys? [closed]
  22. Algorithm to fill triangle
  23. Shuffle list, ensuring that no item remains in same position
  24. Sorting in place
  25. Given a number, produce another random number that is the same every time and distinct from all other results
  26. Painter puzzle – algorithmic estimation from first principles
  27. Polynomial time and exponential time
  28. How to count integers between large A and B with a certain property?
  29. Why is depth-first search claimed to be space efficient?
  30. maximum subarray of an array with integers [duplicate]

Leave a Comment