IITKP206 - Editorial

Problem link

contest
practice

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