Optimal Batching for Synchronized Production

🎯 Level: Easy ⭐ Score: 30 ⏱️ Estimated Time: 30 mins
📜 Problem Description

In modern manufacturing, optimizing workflows and resource allocation is crucial. Consider a scenario where a factory operates two independent production lines, Line A and Line B. Each line completes a production cycle, yielding a specific number of components.

For efficient quality control, packaging, or further assembly, the factory aims to group components into the largest possible standardized batches. An "optimal batch size" is one that allows for complete utilization of components from both Line A and Line B for a given cycle, meaning the batch size must perfectly divide the total components produced by Line A, and also perfectly divide the total components produced by Line B. No components should be left over when forming these batches.

Your task is to determine this largest optimal batch size given the number of components produced by Line A and Line B in a single cycle. This is equivalent to finding the Greatest Common Divisor (GCD) of the two production counts.

For instance, if Line A produces 12 units and Line B produces 18 units, the numbers that divide both are 1, 2, 3, 6. The largest among these is 6. So, the optimal batch size would be 6.

Input Format

The first line contains an integer T, indicating the number of test cases.

For each test case, a single line follows containing two space-separated integers, A and B, representing the number of components produced by Line A and Line B, respectively.

Output Format

For each test case, print the largest optimal batch size (i.e., the GCD of A and B) on a new line.

Constraints

  • 1 <= T <= 100
  • 1 <= A, B <= 100000
📌 Constraints
1 <= T <= 100; 1 <= A, B <= 100000
📝 Sample Input/Output

    
Sample Input

    
3
4 5
3 6
6 8

    
Expected Output

    
1
3
2

    
Explanation

    
Test Case 1: For Line A producing 4 units and Line B producing 5 units.

    
    
        
  • Divisors of 4: 1, 2, 4
    • 
        
  • Divisors of 5: 1, 5
    • 
        
  • The only common divisor is 1. Thus, the largest optimal batch size is 1.
    • 
    

    
Test Case 2: For Line A producing 3 units and Line B producing 6 units.

    
    
        
  • Divisors of 3: 1, 3
    • 
        
  • Divisors of 6: 1, 2, 3, 6
    • 
        
  • The common divisors are 1, 3. The largest among these is 3. Thus, the optimal batch size is 3.
    • 
    

    
Test Case 3: For Line A producing 6 units and Line B producing 8 units.

    
    
        
  • Divisors of 6: 1, 2, 3, 6
    • 
        
  • Divisors of 8: 1, 2, 4, 8
    • 
        
  • The common divisors are 1, 2. The largest among these is 2. Thus, the optimal batch size is 2.
    •
💡 Hints
  • 💡 The problem asks for the Greatest Common Divisor (GCD) of two numbers. Recall the definition of GCD.
  • 💡 Consider using the Euclidean algorithm, which is an efficient method to compute the GCD of two integers. It's based on the principle that GCD(a, b) = GCD(b, a % b) until b becomes 0.
  • 💡 The Euclidean algorithm can be implemented both iteratively (using a loop) or recursively. Choose the approach that you find most intuitive.
📚 Topics

Math & Bit Manipulation

🏢 Asked By Companies

Adobe, Amazon, Paytm

😕 No submissions found

Start coding and your submissions will appear here.