I recently saw a question and was stuck on it for quite some time. ↵
Let's say if there are 'n' people standing is a circle. Now I will talk to the 1st person, then skip next 'a' people and talk to (a+2)-th person. I am supposed to calculate the number of people I have to talk to, before I can talk to the 1st person again.↵
↵
Eg 1:↵
The number of people = 10.↵
The number of people to skip = 3.↵
↵
so, the order in which I will go to people is -> 1 5 92 6 10 3 7 1↵
here, we can see that I had to go through94 people to reach to 1 again.↵
↵
Eg 2:↵
The number of people = 10.↵
The number of people to skip = 1↵
↵
the order to reach out to people -> 1 3 5 7 9 1↵
here, 4 people were visited before reaching to 1 again.↵
↵
Now the naive approach to solving this problem will be to iterate over the array but that will give me a time complexity of O(n) but if the number of people standing in the circle is of the order 10^18. This will not work.I think a better way to approach this problem would be by the help of gcd operation but I am not able to figure out the correct specifics of that approach.↵
Also, Is there a approach to solve these type of questions.
Let's say if there are 'n' people standing is a circle. Now I will talk to the 1st person, then skip next 'a' people and talk to (a+2)-th person. I am supposed to calculate the number of people I have to talk to, before I can talk to the 1st person again.↵
↵
Eg 1:↵
The number of people = 10.↵
The number of people to skip = 3.↵
↵
so, the order in which I will go to people is -> 1 5 9
here, we can see that I had to go through
↵
Eg 2:↵
The number of people = 10.↵
The number of people to skip = 1↵
↵
the order to reach out to people -> 1 3 5 7 9 1↵
here, 4 people were visited before reaching to 1 again.↵
↵
Now the naive approach to solving this problem will be to iterate over the array but that will give me a time complexity of O(n) but if the number of people standing in the circle is of the order 10^18. This will not work.I think a better way to approach this problem would be by the help of gcd operation but I am not able to figure out the correct specifics of that approach.↵
Also, Is there a approach to solve these type of questions.
