https://www.acmicpc.net/problem/1188
initial
I actually thought if there are more peeps than sausages, we dont have to cut cuz we just keep whatever is left. But the question asked to distribute all of the sauasages equally (no leftover). So I had to rethink
solution
The pattern is that if number of sausages is divisible by number of peeps like 6%3=0, then we dont have to cut. Else, we find the gcd and do num of sausages-gcd. This is cuz at worse case where gcd=1 like 6 saus, 7 peeps, then we have to cut by number of peeps -1 (gcd).
num,den=map(int,input().split())
def gcd(a,b):
if a%b==0:
return b
return gcd(b,a%b)
print(den-gcd(num,den))complexity
The time complexity of this code is determined by the Euclidean algorithm used to calculate the greatest common divisor (gcd) of num and den. The Euclidean algorithm has a time complexity of O(log(min(num, den))), which is quite efficient.
The den - gcd(num, den) operation also has a time complexity of O(log(min(num, den))) because it involves calculating the gcd.
Therefore, the overall time complexity of this code is O(log(min(num, den)).
The space complexity is O(1) as there are no data structures that grow with the input size, and the recursion in the gcd function is a tail-recursive call, which doesn't increase the space complexity.
