justin = { main feed , music , code , askjf , pubkey };
Ask Justin Frankel
No reasonable question unanswered since 2009!

Suggested topics: programming, music, sleep, coffee, etc.

Note: please do not ask questions about REAPER features, bugs or scheduling, use the forums instead.

Name: Ask: Human (enter yes):
[back to index] | [unreplied] | [replied] | [recent comments] | [all]

Question: Quick Fun Puzzle : Given an array of size n, with elements in the range [1, n-1], it contains only one duplicate element example (1,2,2,2,3) , How would you get this duplicate in constant space ?
Asked by zeof (156.195.98.x) on July 9 2023, 4:12am
Reply on July 9 2023, 12:56pm (edited at July 9 2023, 1:02pm):
    I assume I can't sort the list because that wouldn't be constant space? Anyway since you don't care about time, the O(N^2) algorithm of checking each element against every later element would be the most obvious way?

    Edit: ah, your example confused me, I assume your example is (1,2,2,3) rather than the extra 2? And I also assume (1,3,2,2) would be another valid example (e.g. the list is not necessarily sorted). Anyway there's probably some ways to reduce the complexity of the above search, but since you didn't specify a desired performance characteristic I wouldn't bother!


    Your Name:   -- Site Owner's Name:  (for human-verification)


[back to index] | [unreplied] | [replied] | [recent comments] | [all]
Copyright 2023 Justin Frankel. | RSS