Interview Algorithms: Difference between revisions
| Line 14: | Line 14: | ||
then you count the number of times each bit appears and take it mod <math>n</math>.<br> | then you count the number of times each bit appears and take it mod <math>n</math>.<br> | ||
The remaining bits will remain <math>m \mod n</math> times.<br> | The remaining bits will remain <math>m \mod n</math> times.<br> | ||
* [https://leetcode.com/problems/single-number/ single-number] | |||
* [https://leetcode.com/problems/single-number-ii/ single-number-ii] | |||
* [https://leetcode.com/problems/single-number-iii/ single-number-iii] | |||
Revision as of 18:24, 8 January 2020
Insights from Leetcode problems.
Finding a cycle in a linked-list
Use two runners. \(\displaystyle O(n)\)
Runner 1 goes two steps per iteration.
Runner 2 goes one step per iteration.
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.
Finding duplicates in an array
If you have an array of ints where each number appears \(\displaystyle n\) times and one number appears \(\displaystyle m\gt n\) times where \(\displaystyle gcd(n,m)==1\),
then you count the number of times each bit appears and take it mod \(\displaystyle n\).
The remaining bits will remain \(\displaystyle m \mod n\) times.