Tortoise and hare 활용

문제) Array A of N+1 numbers, all in between 1~N, where there is only one number with duplicates (≥ 2)

https://www.youtube.com/watch?v=pKO9UjSeLew&ab_channel=JomaTech

 

Time O(N)

Space O(1) 솔루션?

→ Tortoise and hare 활용;

 

배열 index = node,

배열 값 = 다음 node로의 포인터

라고 생각하면, graph 떠올릴 수 있음.

 

중복되는 배열 값이 존재 = Cycle 존재 = Tortoise and hare 알고리즘으로 찾아내기

(참고로, 한 숫자가 여러 번 나타나는 duplicate도 괜찮음. 아예 배열이 한 숫자로만 채워져있어도 됨. Cycle 무조건 생기므로)

 

 

🌟 <알고리즘 Proof>

- https://www.youtube.com/watch?v=9YTjXqqJEFE (이것도 tortoise가 cycle 진입 후 hare를 만나기까지는 1 cycle을 채 돌지 않는다는 가정을 깔고 있어서 뭔가 거슬림. 알아서 증명하라고는 하는데 흠)

- https://goldenriver42.tistory.com/46 ('More general proof' 보기)

 

👍 번외 : 'XOR 활용' 으로도 문제 해결 가능.

1~N 숫자랑 배열 수들 모조리 XOR (^) 해버리면, 배열 수들은 모두 crossed-out 돼서 사라지고, 중복된 숫자 하나만 남게 됨.

(https://goldenriver42.tistory.com/73 맨 마지막 'XOR 활용한 중복 제거')