Timeline for You are given a file which contains all possible numbers on a 32-bit architecture. 4 numbers are missing from that file. Find the 4 missing numbers
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2016 at 17:38 | history | edited | user949300 | CC BY-SA 3.0 |
added 622 characters in body
|
| Oct 20, 2016 at 17:29 | comment | added | user949300 | @JoulinRouge (and JacquesB) So, we agree that this is linear in time, uses modest (1/2 Gig) RAM, and only takes one pass of I/O. Works for me. | |
| Oct 20, 2016 at 13:46 | comment | added | JacquesB |
@user949300: nextClearBit() has an overload which takes a start index to search from, so you still only need one full traversal, regardless of how many missing numbers.
|
|
| Oct 20, 2016 at 8:04 | comment | added | JoulinRouge | @user949300 it's called 4 times but it is still linear. Also i don't need to start from the beginning of the array every time i find a missing number. When I find a missing number I can just go on till i find the next one (I would need a custom implementation of nextClearBit). I think that's the optimal solution since you have to scan all the input at least once. | |
| Oct 20, 2016 at 5:19 | comment | added | Display Name | missing numbers can be collected all in one pass | |
| Oct 20, 2016 at 5:06 | comment | added | user949300 |
nextClearBit() will be called 4 times. If there were many many missing numbers this would slow down.
|
|
| Oct 19, 2016 at 22:42 | comment | added | JacquesB |
@JoulinRouge: BitSet uses an array of ints as underlying storage, so set() is constant. nextClearBit is O(n), but only called once, so I believe the whole algorithm is O(n).
|
|
| Oct 19, 2016 at 15:10 | comment | added | JoulinRouge | what's the computational complexity of BitSet.set(value) and BitSet.nextClearBit()? If it's O(n) your solution is very slow, if it's constant your solution may be the optimal one | |
| Oct 17, 2016 at 14:41 | comment | added | user949300 | @CodesinChaos good catch on Integer.MIN_VALUE. Code editied, though it's 7 in the morning here so I wouldn't trust it completely. :-) | |
| Oct 17, 2016 at 14:41 | history | edited | user949300 | CC BY-SA 3.0 |
edited code to account for CodesInChaos comment
|
| Oct 17, 2016 at 11:52 | comment | added | CodesInChaos |
If the language of choice has no built in bitsets, emulating them by using a byte array. For example in C#: bool GetBit(byte[] byteArray, uint index) { var byteIndex = index >> 3; var bitInByte = index & 7; return (byteArray[byteIndex] >> bitInByte) & 1 != 0; }
|
|
| Oct 17, 2016 at 11:47 | comment | added | CodesInChaos | This naive approach needs 2^32 bits = 4 Gib = 512 MiB for the bitsets, which is a modest amount of RAM, even on a 32-bit system. | |
| Oct 17, 2016 at 11:46 | comment | added | CodesInChaos |
Doesn't handle Integer.MIN_VALUE correctly. You could mask out the sign bit instead of negating to fix it.
|
|
| Oct 17, 2016 at 3:59 | comment | added | user949300 | @Idan Ayre. This solution requires little code, so less chance of coding errors. I'm pretty this is time O(n). Nor does it assume/require multiple passes through a huge file, so it uses less space than an algorithm requiring multiple passes. Please elaborate what you mean by "Oh dear". | |
| Oct 17, 2016 at 0:39 | history | answered | user949300 | CC BY-SA 3.0 |