Problem Link - Apples and oranges in Number theory
Problem Statement:
Rushitote wants to distribute N apples and M oranges equally among contestants. The goal is to find the maximum number of contestants such that each contestant gets an equal number of apples and oranges without any leftovers.
Approach:
- The solution is to find the greatest common divisor (GCD) of N and M, as it represents the maximum number of contestants who can evenly divide both the apples and oranges. Each contestant will get N/GCD(N, M) apples and M/GCD(N, M) oranges.
- To calculate the GCD: GCD(a, b) = GCD(b, a % b) This means the GCD of two numbers doesn’t change if the larger number is replaced by its remainder when divided by the smaller number. The process keeps reducing the size of the numbers, eventually reaching a remainder of 0.
Complexity:
- Time Complexity:
O(log(min(N, M)))The algorithm reduces one of the numbers by at least half at every step, making it very efficient for even large numbers. - Space Complexity:
O(1)No extra space required.