Zoo creatures - The smallest number of creatures so they can grab each other hands (Super Easy)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Solve on HackerEarth

Problem
    
A zoo have two types of creatures, type A has a hands and type B has b hands. Spawn the smallest number of creatures so they can grab each other hands in the following conditions:

Each creature should only grab the hands of another creature type.
Each creature should grab with all of its hands.

What is the smallest number of creature needed?

Note: It is guaranteed that under the given conditions answer is unique.

Input format

The first line contains 
 number of test cases .
Each of the next 
 lines contains two integers 
 denoting the number of type A creature hands and the number of type B creature hands.
Output format

The output contains 
 lines. For each test case, print two numbers 
, the number of type A creatures, and the number of type B creatures. Consider that 
 should be smallest possible.

Constraints



Sample Input
1
20 2
Sample Output
1 10
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
At least 1 of each creture types needed.

One creature of type A has 20 hands.

Ten creatures of  type B have 20 hands.

So they can grab each other hands in asked conditions.

My Code

import math

def solve(a, b):
    l = math.lcm(a, b)
    return (l//a, l//b)

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    out_ = solve(a, b)
    print(out_[0], out_[1])

---

---

User: how to calculate lcm and hcf for two numbers in python?

In Python, you can calculate HCF (GCD) and LCM very easily using the built-in math module.

---

✅ 1️⃣ HCF (GCD – Greatest Common Divisor)

Using built-in function (Recommended)

python
import math

a = 12
b = 18

hcf = math.gcd(a, b)
print(hcf)

Output:

6

---

✅ 2️⃣ LCM (Least Common Multiple)

Python 3.9 and above (Best way)

python
import math

a = 12
b = 18

lcm = math.lcm(a, b)
print(lcm)

Output:

36

---

🧠 If using Python older than 3.9

You can compute LCM using GCD:

Formula:

$$LCM(a, b) = \frac{a \times b}{GCD(a, b)}$$

Code:

python
import math

a = 12
b = 18

lcm = abs(a * b) // math.gcd(a, b)
print(lcm)

---

📌 Without using math module (Manual GCD – Euclidean Algorithm)

python
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

print(gcd(12, 18))
print(lcm(12, 18))

---

🎯 What’s happening internally?

GCD uses the Euclidean algorithm:

Example for 12 and 18:

matlab
18 % 12 = 6
12 % 6 = 0
→ GCD = 6

---

🚀 Quick Summary

Operation	Function
HCF / GCD	math.gcd(a, b)
LCM	math.lcm(a, b) (Python 3.9+)
Older Python LCM	(a*b)//math.gcd(a,b)

---

If you want, I can also explain:

• Why Euclidean algorithm works

• How to compute LCM for multiple numbers

• Relationship between LCM and GCD

• Time complexity analysis