3 ms·
Another one is: you have a list of numbers, more than half of them are the same number, and you have to find it. Ex: 1 2 3 1 1 3 1 => 1 Hints 1- It can be do
by GuB-42 5y ago
Another one is: you have a list of numbers, more than half of them are the same number, and you have to find it.
Ex: 1 2 3 1 1 3 1 => 1
Hints
1- It can be done in one pass, linear time, constant space
2- It doesn't have to be numbers
3- The algorithm it is literally just 2 statements in a loop
- comex 5y agoAre you allowed to modify the list? Edit: I think I figured it out!
- rowanG077 5y agoFeatures in this video: https://www.youtube.com/watch?v=pKO9UjSeLew https://www.youtube.com/watch?v=pKO9UjSeLew
- wahern 5y agoAccording to the solution in the video, the problem upthread was stated incorrectly. There's an additional constraint that only integers in the interval [1, N], where N is the size of the array, are permitted; or at least where the numbers can be trivially mapped to that interval (e.g. subtraction of an offset).