justin = {
main feed
,
music
= {
decanted youth
,
yes, exactly, yes!
,
not vampires
,
full archive
}
,
code
= {
cockos
,
reaper
,
wdl
,
ninjam
,
jsfx
,
more
}
,
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!
Comments:
Posted by zeof (156.195.98.x) on July 9 2023, 2:19pm:
Well an O(n^2) is definitely correct but an O(n) time and O(1) space is more "fun", you cannot assume the array is sorted, and although only a single element is duplicated it can be duplicated many times not just once like (1,2,2,3,4) (1,2,2,2,4) (2,2,2,2,4) are all valid
Posted by
Justin
on July 10 2023, 3:17pm:
For O(N), I do think you'd need to modify the underlying array... anyway
Posted by brumbear (69.172.168.x) on July 11 2023, 6:56am:
this:
en.wikipedia.org/wiki/Cycle_detection
Posted by brumbear (69.172.168.x) on July 11 2023, 6:58am:
sadly, I see no obvious use for audio with this.... lalala
Comment:
Your Name:
-- Site Owner's Name:
(for human-verification) Comment:
[
back to index
] | [
unreplied
] | [
replied
] | [
recent comments
] | [
all
]
Copyright 2024 Justin Frankel
.
|
RSS