LMP3 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an integer N.
In one operation, you can reorder the digits of N (while ensuring there are no leading zeros), or subtract any digit of N from it.

Find the minimum number of operations needed to make N odd.

EXPLANATION:

An odd number is one whose last digit is one of \{1, 3, 5, 7, 9\}.

If N is already odd, the answer is 0.
So, we assume N is even from here.

Next, we check if the answer is 1.
If N contains one of the digits \{1, 3, 5, 7, 9\} already, one operation will suffice: just reorder the digits and place the odd digit at the end.
Otherwise, all the digits of N are even. In this case, subtracting an even digit from an even number will still result in an even number; so one subtraction can’t help us either.
Thus, the answer must be at least 2.

Next, we check for the answer being 2.
Note that if we’re here, we’ve reached the case where N is even and all the digits of N are also even.
Now, with two operations:

  • Performing two shuffles is useless, we can’t obtain an odd number like that.
  • We could perform one subtraction and then a rearrangement.
    This will be valid if the subtraction gives us an odd digit (say, in the tens place), which we can then use the rearrangement to place in the end.
    This case can be checked by just performing every possible subtraction and looking at the resulting number.
  • Performing a rearrangement followed by a subtraction is also useless: after rearrangement the number still has all even digits, so digit subtraction cannot make it odd.
  • Performing two subtractions could work, but only if the first subtraction creates an odd digit (which we then use for the second subtraction).
    However, this case is already covered in the subtract → shuffle case so we don’t really need to check for it.

Thus, checking for answer = 2 only needs a single check: if subtracting some digit from N results in an odd digit.

Finally, if even the answer = 2 check fails, the answer must be at least 3.

Here, we see that it’s (almost) always possible to obtain an answer of 3, because we can do the following:

  • Subtract the last digit of N. It now ends with 0.
  • Subtract the highest digit of N. The tens place will now change to an odd digit.
  • Rearrange the number to place the odd digit at the end.

However, this does require N to have a tens digit in the first place.
So, if we’ve reached this case but N \lt 10, no solution exists.
Otherwise, the answer is 3.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
def has_odd(n):
    for d in [1, 3, 5, 7,9]:
        if str(d) in str(n): return True
    return False

for _ in range(int(input())):
    n = int(input())
    
    if n%2 == 1: print(0)
    elif has_odd(n): print(1)
    else:
        ans = 3 if n >= 10 else -1
        for d in str(n):
            if has_odd(n - int(d)): ans = 2
        print(ans)