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 9 3 7 1 here, we can see that I had to go through 4 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.

I was recently solving a problem on Hacker-Earth and there was a particular subtask I needed to complete to submit the solution successfully. Say, I am given an array of integers.pick a pair (i,j) such that 'i' is less than 'j'. The task was to find out the number of times this pair will occur in all the contiguous subarrays of the given array.

for example : number of elements — n = 5; given array — 1 2 3 4 5

subarrays of given array — (1,2) (2,3) (3,4) (4,5) (1,2,3) (2,3,4) (3,4,5) (1,2,3,4) (2,3,4,5) (1,2,3,4,5)

pair (1,2) occurs 4 number of times in subarrays (1,2) , (1,2,3) , (1,2,3,4) and (1,2,3,4,5); similirialy, pair (3,4) occurs 6 number of times in subarrays (3,4) , (2,3,4) , (3,4,5) , (1,2,3,4) , (2,3,4,5) , (1,2,3,4,5);

Now, I found that for every pair (i,j) such that i<j, can find it ** (n-j+1)*i ** number of times. Can anybody please explain with mathematical proof, why this particular expression is working?

Thank you.