Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Midweek challenge: Which number is missing from the list?

 
Sheriff
Posts: 4870
317
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I came across this little programming challenge earlier in the week and figured I'd share it for you guys to enjoy as well.

Q: Given an ordered list of unique integers ranging from 0 to n, where n is very large. If a single integer is removed from the list and the list order is randomised, can you propose an algorithm that would determine which integer was removed?
 
Bartender
Posts: 598
26
Oracle Notepad Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, in SQL, the method of counting is done by the database and order does not matter, so a brute force count would do it. I see 3 easy solutions, a recursive loop looking for the number, but that could be very expensive if the numbers are not in order. A GROUP BY/HAVING COUNT(X) = 1 could be used against another set of numbers, but that requires generating a second list before the group by starts, and the group by would need to sort the numbers. So, i say, sum the numbers, and subtract that from what the the total ought to be: n*(n-1)/2 and you are left with the missing number.
 
Tim Cooke
Sheriff
Posts: 4870
317
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Very nice Brian. Have a cow
 
Marshal
Posts: 69752
277
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There has to be a way to use a Stream:-I do not know what size the collection is; if it is very large I would consider changing the Streams to LongStreams instead.
 
Brian Tkatch
Bartender
Posts: 598
26
Oracle Notepad Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:[code=java]long expectedSum = ((long)summary.getMax() + summary.getMin()) * summary.getCount() / 2;


I know n*(n+1)/2, and i know there's a more complicated equation for sequences, but, what does that do? You need to get the maximum number, but the minimum, per the question, is 0 (unless that is the missing number).

Hmm...If you are told the maximum number, n*(n+ 1)/2 will get what the max should be for sure. Subtracting actual max from real max will give you the result, even if it is 0. Whatever it is, that is the missing number. However, if you do not know the maximum number, and the result is 0, the missing number can be either 0 or the max number + 1. Meaning, on 0, you would have to check the data specifically for 0 (by existence, or if count + 1 == the sum).
 
Campbell Ritchie
Marshal
Posts: 69752
277
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If heap space is not an issue:-
 
Campbell Ritchie
Marshal
Posts: 69752
277
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Brian Tkatch wrote:. . . the minimum, per the question, is 0 (unless that is the missing number). . . .

I had forgotten that the minimum was 0. In that case the simpler technique of adding 1 to the size of the list give the maximum and
n*(n+1)÷2 gives the expected total.
 
Campbell Ritchie
Marshal
Posts: 69752
277
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Set up a BitSet size + 1, and set all its bits. Iterate the List and clear each bit in the BitSet, but one. Iterate the BitSet and the remaining set bit is the missing number.
 
lowercase baba
Posts: 12870
62
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:In that case the simpler technique of adding 1 to the size of the list give the maximum and
n*(n+1)÷2 gives the expected total.


Does the problem state that ALL integers are present between 0 and n? I didn't read it that way. My interpretation was that the smallest was 0, the largest was n, and nothing is duplicated, but that this would be a valid list:

n=209329409542

0,1,7,43,186,209329409542

 
Brian Tkatch
Bartender
Posts: 598
26
Oracle Notepad Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:Does the problem state that ALL integers are present between 0 and n?


"If a single integer is removed from the list" If just a single integer is removed, there has to be a way of telling what it is, and that is done by comparing it against a complete list.
 
Bartender
Posts: 3993
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm. it's a bit of a nonsense problem, I'm afraid.
Either Fred is correct, but then we need both lists to determine the difference,
or indeed we have all consecutive integers from 0 to n, but in fact we then also have
the original list at hand.

So, I wonder, why are we given the 0 and the n, and that n is "very large", since that is totally irrelevant?
 
Tim Cooke
Sheriff
Posts: 4870
317
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good analysis of the question and you have highlighted a point of ambiguity. Is every number between 0 and n present? Yes, the question would be better phrased "Given an ordered list of sequential integers ranging from 0 to n ...".

e.g. [0,1,2,3,4,5,...,n]

The "very large" part of the question was to discourage algorithms that walked the list multiple times or generated new similarly huge lists.
 
Ranch Hand
Posts: 385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Cooke wrote:Good analysis of the question and you have highlighted a point of ambiguity. Is every number between 0 and n present? Yes, the question would be better phrased "Given an ordered list of sequential integers ranging from 0 to n ...".

e.g. [0,1,2,3,4,5,...,n]

The "very large" part of the question was to discourage algorithms that walked the list multiple times or generated new similarly huge lists.



I didn't think the question was ambiguous - it's impossible to determine which number was removed if there is already some number missing.

I do however think the question could have been reworded to "Given [0..P | P ∈ N] and P is very large, if a number is randomly removed, find it".
 
Brian Tkatch
Bartender
Posts: 598
26
Oracle Notepad Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ahmed Bin S wrote:if a number is randomly removed, find it".


There's are so many fun ways to break apart the formulation of this instruction.

If a number is removed random, it might still be there.
Of course, if a random number is removed, we're probably not dealing with integers.

Just having fun.
 
Tim Cooke
Sheriff
Posts: 4870
317
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ahmed Bin S wrote:"Given [0..P | P ∈ N] and P is very large, if a number is randomly removed, find it"


Is it down the back of the sofa?
 
Ahmed Bin S
Ranch Hand
Posts: 385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Brian Tkatch wrote:

Ahmed Bin S wrote:if a number is randomly removed, find it".


There's are so many fun ways to break apart formulation of this instruction.



My point was that if you use that notation, then you don't need to talk about order and sequential, so the question becomes more concise.
 
Ahmed Bin S
Ranch Hand
Posts: 385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Cooke wrote:

Ahmed Bin S wrote:"Given [0..P | P ∈ N] and P is very large, if a number is randomly removed, find it"


Is it down the back of the sofa?



Only if it's the final number that wins me the lottery!
 
Brian Tkatch
Bartender
Posts: 598
26
Oracle Notepad Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ahmed Bin S wrote:

Tim Cooke wrote:

Ahmed Bin S wrote:"Given [0..P | P ∈ N] and P is very large, if a number is randomly removed, find it"


Is it down the back of the sofa?



Only if it's the final number that wins me the lottery!


You're having a ball with this, aren't you?
 
Don't get me started about those stupid light bulbs.
    Bookmark Topic Watch Topic
  • New Topic