1
00:00:00,120 --> 00:00:01,680
OK, guys, Hilbert's Hotel.

2
00:00:02,130 --> 00:00:03,050
Now it's time to see the good.

3
00:00:03,640 --> 00:00:04,560
Let's see what I did here.

4
00:00:05,760 --> 00:00:06,980
So it's accepted.

5
00:00:07,430 --> 00:00:07,890
All right.

6
00:00:08,790 --> 00:00:11,040
So was I've seen as we've seen together.

7
00:00:11,760 --> 00:00:15,930
I am reading the number of tests and for each and every test I am reading.

8
00:00:16,030 --> 00:00:17,730
And the number of rooms.

9
00:00:18,150 --> 00:00:23,730
And then I am initializing a vector of Borland's of size and plus one.

10
00:00:24,030 --> 00:00:24,270
Right.

11
00:00:25,500 --> 00:00:26,340
Only with force.

12
00:00:26,370 --> 00:00:26,640
Right.

13
00:00:26,670 --> 00:00:28,560
This is the frequency array.

14
00:00:28,770 --> 00:00:31,250
The visited array are unrecorded then.

15
00:00:31,440 --> 00:00:34,710
What I do is that I read of course the array.

16
00:00:35,730 --> 00:00:42,630
And for each and every number which I will call X if this number is less than zero.

17
00:00:42,690 --> 00:00:50,190
So as we've talked about, what we have to do is that this X is going to be increased by a number large

18
00:00:50,190 --> 00:00:51,810
enough to make it positive.

19
00:00:52,500 --> 00:00:54,910
Which I called infinite crossed and.

20
00:00:55,270 --> 00:00:55,520
Right.

21
00:00:55,620 --> 00:00:58,200
This is very important because you have to increase it.

22
00:00:58,230 --> 00:01:06,680
We have a large number which also won't affect the final reminder modulo M of X.

23
00:01:06,720 --> 00:01:07,020
Right.

24
00:01:07,260 --> 00:01:12,030
So X becomes X plus infinite crossed and which is a multiple of N.

25
00:01:12,420 --> 00:01:18,600
So this expression has the same reminder modulo N as X, which is good.

26
00:01:18,960 --> 00:01:19,760
It doesn't affect that.

27
00:01:19,770 --> 00:01:19,920
Right.

28
00:01:20,760 --> 00:01:26,010
So this infinity is something like I don't know how many zeros I have here.

29
00:01:26,340 --> 00:01:27,610
It looks like I have nine zero.

30
00:01:27,630 --> 00:01:28,680
So then a power nine.

31
00:01:29,100 --> 00:01:29,350
Right.

32
00:01:29,370 --> 00:01:36,270
So yeah, you make sure that this is going to be a long, long superimportant, so infinite crust and

33
00:01:36,270 --> 00:01:39,750
everything long, long increased by X and everything modulo M.

34
00:01:40,200 --> 00:01:41,950
And this is the new X.

35
00:01:42,090 --> 00:01:45,520
Instead it was negative.

36
00:01:46,050 --> 00:01:54,120
And now because we know this X, we just go and take a look at the reminder of EI plus X modulo N,

37
00:01:54,900 --> 00:01:59,850
and if it was already encountered, we just see out as we've talked about and break.

38
00:02:00,090 --> 00:02:06,530
If not, we just make sure that we mark it as seen or urs encountered.

39
00:02:06,690 --> 00:02:09,600
So rest of that expression equals true.

40
00:02:09,930 --> 00:02:14,760
And then if this y loop terminates, there are two possible scenarios.

41
00:02:14,790 --> 00:02:18,170
It either terminated organically when I.

42
00:02:18,210 --> 00:02:18,990
Equals M.

43
00:02:19,020 --> 00:02:22,200
So here if it did so then we see out.

44
00:02:22,230 --> 00:02:22,410
Yes.

45
00:02:22,440 --> 00:02:28,160
Because everything is valid or it ended with this break because we printed.

46
00:02:28,170 --> 00:02:28,460
No.

47
00:02:28,590 --> 00:02:31,390
So we already know the solution is bad.

48
00:02:31,410 --> 00:02:32,200
So that's it.

49
00:02:32,220 --> 00:02:32,490
Right.

50
00:02:32,850 --> 00:02:35,220
So that all you have to do.

51
00:02:35,610 --> 00:02:36,210
Simple as that.

52
00:02:36,210 --> 00:02:37,410
Has seen that extend.