It's kind of a geeky maths question, but it's actually pretty nice.
No, I think Hilbert's hotel is from something like Hilbert's curve or some function.
And I don't know this guy Hilbert was some math guy who I think had some fury about the infinite numbers
or something.
But anyways, let's read the statement.
So as you probably know, you are given this hotel and basically you have an infinite number of rooms
from minus infinite to plus infinite.
And there is exactly one person staying in each of these rooms called everything and not normal for
a hotel right now.
But the interesting thing is that you are given an array.
Right.
Just called a and has an integers.
And what happens is that for each number key.
So for each room, which has no key.
Of course from minus infinity.
Plus infinite.
The guy who is staying in that room, number K, is now going to be asked to leave that room and go
to room number K plus A. of K modulo N.
And this module is.
Yeah.
They give us some definition for this module, but we are gonna get into it.
So let's see how I thought about this problem.
So let's take some examples first.
Right.
I have basically read this problem.
And of course, first thing I know, it's a math stuff.
And basically, when you're reading on good force is a problem that's about math.
You usually have to get your pen and paper close to you.
I didn't do that.
I took my risk and it turned out I can solve it.
Like only thinking about it, not writing anything.
So let's see.
Let's take some examples.
What I did is I go look at these examples and let's take the first one, which is quite interesting.
So we have four elements, right?
We are given four elements.
Four, they are not the rooms either or for the four elements and equals four.
Whatever.
So any plans for.
And the array A is by.
I've and I think the last element was what?
Sure.
Was it?
Yes, it was one, so that's what happens here.
First of all, let's index these integers, right?
Zero, one, two and three.
And let's try to imagine the rooms of our.
To have here it's I'm going to use my drawing skills, so minus infinity.
Minus infinite, plus one.
And so on and so forth.
Number zero.
Room number one and so on and so forth.
And they'll, of course.
Room number infinite.
And don't ask me how I know this is room number infinite because I don't.
But let's imagine we can get in front of room number infinity or minus infinity, right?
If we had superpowers or something.
So basically, let's imagine all the rooms in our hotel.
Right.
Binding the roll call.
And let's see what happens.
Well, as we said, the guy in rule number case is asked to leave the room and move to Kate plus eight.
Of I think it was the AK modulo and.
Cool.
So let's see what they did here.
I have taken a look at this formula and I see.
Free, let's say, letters.
We just keep.
And and cool.
So they basically see here is some integer key.
Which is between minus infinite and infinite and some integer A of K modulo M, which from, of course,
the input array.
So I'm thinking like this.
All right, man, I have two integers.
One of them is infinite.
Could be anything I can possibly fix the key or something like that.
Right.
So I really have to.
Do something with this.
But what they basically did is that.
Because Kee.
Can take an infinite.
Of possible values.
Eight of Kay modulo and.
Take only impossible values.
Right.
Because there are values in disarray.
So there are.
And possible.
Boy, did I do I didn't fix Kay because no one can do that.
But I have fixed Kay modulo.
I have fixed each and every key module and of course.
This is between zero and minus one.
That's the first thing I know I have to do.
And let's start from the beginning.
Let's take the case in which key module N is equal to zero.
Let me erase this down here and see what happens.
What's going to happen on Teneriffe?
Number one.
Kay Modula.
Well, first of all, let's take a look at a zero, which is five.
What does the problem tell us?
That the guy in each and every no key.
Which is now a multiple of em.
Right.
Because we have set this reminder, we know it right now.
So what are the possible values?
Which is this room then?
Could be an.
Let's say here.
We have room.
No n.
Could be cross then.
We have room.
Number two, cross that.
So on and so forth, of course, infinite Vellis here.
And also, there are negative versions.
Right.
Which is minus two crossed.
Minus four crust and.
So here I have.
Some doors.
Some rooms.
Minus two, cross that and so on and so forth.
What happens is that I can imagine that all these guys are taken out of these rooms and they are shifted
by five.
That's all they are, just shifted by five.
Bus five and so on and so forth.
This hotel is infinite.
There is actually one thing which we can mathematically notice about these numbers.
What happens is that we kind of rebind these numbers what used to be zero.
Is No.
Five, what used to be N is now and plus five and so on and so forth.
So what I did is the following thing, if I can imagine an array of infinite numbers from minus infinite
to infinite and every value in disarray is one, because there is one guy there on that position.
Which we will call Geary of rooms.
All right.
Well, the array of rooms.
Plus Symphonie, plus one dot, dot, dot zero, one dot, dot, dot.
If.
On this or in disarray is one when Kay modulo n e0, I literally take all these positions.
Position zero.
Xitian minus N position to cross N.
Position minus two crossed in somewhere here.
And all I do is take.
That one here.
And the movie it.
But that position plus five for this example.
So I basically asked myself the following thing.
How can I make sure or how can I check if after performing all these moves basically.
Right.
Subtracting one from here and increasing one here?
Yes.
How can I make sure that the new array.
Let's call it.
Those are free of those, actually.
Let's call it a.
The new array room's prime also has only values of one.
They have to make sure, oh, this.
So basically, I have to make sure that there isn't any position he.
Where there are two.
Positions X and Y.
That are going to be.
Basically to get here.
So I have to make sure that there are in two different rooms, X and Y, that are going to be binded
to the same number.
Basically, I have to make sure that this function, which takes my people from their rooms and move
it to other rooms, is how do you call it?
I can think about the term by objective or something.
I think that's the term for it.
Yes.
So there are not any two different values which are going to be equal.
Having thought about all this.
Get back to this K module.
And now everything is gonna be clear.
This example on this case, on this scenario when Kay modulo any zero.
What happens is that each number.
Each position from this array, which is a multiple of an.
Now is not going to be any more a multiple of an.
But it's a reminder modulo and is going to be five.
Port, this scene aerial.
Where let's say here.
Right.
Kay modulo n zero.
Basically.
Each and every number, which modulo N was zero.
Right.
So it was a multiple of N No.
From multiple of end, let's say something like, I know D crust n.
Is now the crust.
And plus a of zero, which is this value.
So if that number.
Modulo an.
Was zero.
After performing this.
The new number modulo an.
To be a zero.
Well, a zero, of course, modulo an.
So the whole thing that happens here.
One reminder becomes another.
Why do we have to imagine instead of that infinite array of rooms?
Is that these rooms are grouped by the reminder of their index, their number modulo N.
Right.
So on that infinity of numbers, I'm going to have the numbers which modulo N.
Reminder zero, the ones which give reminder, one reminder, too.
And so on and so forth.
Lastly, all the numbers from minus infinity infinite, which modulo n give reminder and minus one.
Of course, there are an infinity of numbers in each of these and groups.
But that doesn't matter.
When I took a of zero.
Each and every number of reminder zero became now a number of reminder, a zero modulo an.
This zero becomes a zero modulo and.
Then what about reminder one?
Well, each number.
Which was.
Something like this right here one.
Each number, which was something like decreased.
And plus what gave reminder one now is going to be increased by a one.
So is D crust and plus a of one plus one.
This reminder was.
A new reminder.
A one, us one and everything.
Module at.
But to what happened?
Exactly the same thing.
So reminder to.
A of two plus two modularly.
And you've got a whole idea.
So what happens is that.
For each and every reminder.
Between zero.
This is going to be transformed, as you've seen, into air plus eight of our.
Everything Modula And.
Did we know this or what?
What did we agree that we will have to check?
Remember we said.
There shouldn't be two rooms X different than Y such that after the transformation.
And as we've seen, because we transform the numbers grouped by reminders.
This can happen.
If and only if.
The reminder of X modulo eight.
A reminder of why modulo.
If these two are different.
Of course, they're reminders are going to be different if this two reminders.
After applying.
The transformation for all the reminders.
Become now.
Same reminder.
Which is Ze modulo n.
So all we have to do.
Each of these numbers are plus eight of our modulo n are also going to be.
Different.
All the values from zero to N minus one.
Right.
So we have basically started from the.
Permutation of all the numbers from zero to minus one in this order.
And we will update.
Another permutation.
Based on the Formula R plus eight of our Modulo n.
Typically, we will obtain an array, and if this array is a permutation that everything is fine because
as I've told you, if this is a permutation.
This means that each two different reminders.
After the transformation are still different.
Right.
So if our one.
And ah, to.
Or different from this permutation and after the transformation, they are still different.
This means that those numbers.
X and Y.
Which were X in group air one and Y in group F two.
What happens after they are transformed?
They're reminders modulo and are different.
Of course, the numbers are going to be all.
Also the.
And that's it.
This is how you solve this problem.
You don't think about the infinite possible values of the room numbers, but you think about their fine,
neat posable reminders modulo and.
And in this way, you have something.
Find it right.
So you can iterate for those elements.
So what they basically did here.
The same thing is the following.
We've basically have iterated through the whole array A.
And I had something like a hash table.
Stable.
Unordered map, an order set frequency array vector from Estill.
It's really your choice.
Let's say it's a harsh day just for the sake of it.
I've got the hash table.
And for each and every element from disarray, I simply checked if that element A of all.
Module An.
Hasn't been encountered.
If this value is not part of my hashtag, if it's not, that's cool, inserted into the hash table and
continue if it is part.
Timperley, return minus.
And that was it.
Just one thing.
The problem was when these numbers.
Because if these numbers are negative, the value AA plus I everything modulo N is not going to be correctly
computed.
What I did, basically, is that if this number is negative, I have increased it by a value like 10
at power line, crossed an.
So I make sure that this final value is positive and also.
The reminder of this value is equal to the reminder of this value modulo.
Right.
Be very careful here because if you take something like minus two.
Modulo 10.
You should get eight for this problem, but you will get minus two, which is a problem.
But if you take this minus two and increase it by something big enough, this becomes eight, which
is greater than zero.
And the reminder modulo 10 is eight, which is indeed the great.
So the problem that I had and I sold it quickly, is to increase this number by something big enough
so it becomes post.
That's it all about the reminders.