multiple hint

5 마리의 비둘기와 5 개의 집이 있습니다.

0 번 집
1 번 집
2 번 집
3 번 집
4 번 집

0 번 집을 사용할 수 없다면 1 - 4 번 집 중 한 곳에는 두 마리의 비둘기가 들어가야 합니다.

이 문제에서 비둘기 수는 수의 개수이고 집은 나머지 입니다.

---

기본적인 루틴은 첫 수부터 순차적으로 더해가면서 N 으로 나눈 나머지를 구합니다.

1. 나머지가 0 이 나오는 경우
   시작 지점 부터 이 지점까지가 N 의 배수가 됩니다. 0 이 나오는 경우는 명확 합니다.

2. 0 이 나오지 않는경우 4 개의 집에는 같은 나머지가 발생하게 됩니다. 같은 나머지가 나왔다는 것은 N 의 배수가 나왔다는 것 입니다. N 으로 나눈 나머지가 같은 두 수를 뺀 수는 나머지가 0 이 됩니다.

   

예를 들어 N = 5 인 경우 두가지 경우를 살펴 보겠습니다.

1. 나머지가 0 인 경우

   수             :6 2 9 8 3  
   나머지         :1 2 4 3
   순차합의 나머지:1 3 2 0
                         *
   

   0 발생 6+2+9+8 이 5 의 배수 입니다.

2. 나머지가 0 이 아닌 경우

   수             :6 3 9 8 3 
   나머지         :1 3 4 3
   순차합의 나머지:1 4 3 1
                   $     *
   

   $ 다음부터 * 까지가 N 의 배수입니다. 즉 3 + 9 + 8 이 5 의 배수.

   :::시간 복잡도 : O(n)