Problem link
Difficulty
cake walk
Pre-requisites
ad hoc
Problem
You are given e even and o odd numbers. In a single operation, you change an even to odd number or vice versa. Find out min number of operations needed to
do such that ratio of even to odd numbers becomes 2 : 3. If it is impossible to do so, output -1.
Solution
Observation 1:
You can see that sum of count of even and odd numbers will be constant because if you increase count of even numbers then count of odd numbers will decrease and vice versa.
Observation 2
If we want ratio of even : odd = 2 : 3. It means that even = 2 * k and odd = 3 * k where k is some integer.
Final Solution
Now if use observation 1, then you can say that 2 * k + 3 * k = n. where n denotes total numbers i.e. e + o.
Rewrite it to 5 * k = n.
So if n is not divislbe by 5, then no solution, So print -1.
Otherwise, we need to have quantity of even numbers = 2 * (n / 5) and odd numbers 3 * (n / 5).
Currently we have e even numbers. We want count of even numbers to be 3 * (n / 5).
- If e > 3 * (n / 5), we will decrease e to become 3 * (n / 5).
- If e < 3 * (n / 5), we will increase e to become 3 * (n / 5).
So total operations needed = |3 * (n / 5) - e| = |3 * ((e + o) / 5) - e|.
Time Complexity
O(1)
Tester’s solution: Will be added Later