MMU has a circular campus. We have N buildings arranged in the campus and one of it is Kyle's faculty. Kyle is currently on the building that is S buildings away from his faculty in the clockwise direction (Means his faculty is S buildings away anti clockwise). Now he'll repeat the move: Go to the building that is K buildings away from the building he is currently in, in clockwise direction. How many moves will it take for him to reach his faculty? If he cannot reach his faculty at all, print -1.
Input Format
First line contains an integer T, the number of testcases. The next line is, N S K.
Constraints
1≤T≤100
2≤N≤109
1≤S≤N
1≤K≤109
Output Format
A single integer, the number of moves to reach his faculty, or -1.
In first test case, Kyle is on the building that is 4 buildings away from the faculty. He will be reaching his faculty after two moves of 3 buildings.
Solution - Optimization Issue
This one can be explained in simple math terms. Since the buildings are in circular, we can convert Kyle's movement as Pm​=(1+m×K)%N, where 1 as Kyle's starting point.
Then, his target can be rewrite to this math expression: (1−S)%N.
*Circular means we can modular the number of buildings to make Kyle keep looping in enclosed cycle.
Then, we can check if the gcd(K,N) is divisible by (1−S)%N. If it is not divisible, this implies that no matter how hard Kyle had walked, he is never reaching the destination, we can eliminate early and print -1.
Otherwise, we can simply simulate the path and track the counter.
But, this question is not that simple. As the third case, which introduces large input, this strategy will hit MemoryError, therefore we need to optimize it:
def min_moves_to_reach_checkpoint(N, K, S):
start = 1
target = (1 - S) % N
visited = set()
moves = 0
while start not in visited:
if start == target:
return moves
visited.add(start)
start = (start + K) % N
moves += 1
return -1
i = int(input())
for _ in range(i):
N, K, S = map(int, input().split())
print(min_moves_to_reach_checkpoint(N, S, K))
The code above hits memory error, therefore we can optimize it by Extended Euclidean Algorithm to get the m, via modular inverse.
Here's the modification of the code, which passed allt est cases:
import math
def min_moves_to_reach_checkpoint(N, K, S):
target = (-S) % N # Target position
g = math.gcd(K, N)
# If GCD does not divide target, there's no solution
if target % g != 0:
return -1
# Reduce the equation by dividing by gcd
N //= g
K //= g
target //= g
# Find modular inverse of K mod N using Extended Euclidean Algorithm
def mod_inverse(a, mod):
g, x, y = extended_gcd(a, mod)
if g != 1:
return None # No inverse exists
return x % mod
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
g, x1, y1 = extended_gcd(b, a % b)
return (g, y1, x1 - (a // b) * y1)
inv_K = mod_inverse(K, N)
if inv_K is None:
return -1
# Calculate the number of moves using modular inverse
moves = (target * inv_K) % N
return moves
i = int(input())
for _ in range(i):
N, K, S = map(int, input().split())
print(min_moves_to_reach_checkpoint(N, S, K))