DIV4 - Editorial

PROBLEM LINK:

Practice

Contest

Author: Prateek Patnaik
Tester: D Teja Vardhan Reddy
Editorialist: Prateek Patnaik

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Math

PROBLEM:

Problem asks you to find a smallest non-negative integer(if possible) that is divisible by 4 by removing some digits(possibly none).The input number will be as large as 1000 digit number.

QUICK EXPLANATION:

It is an important observation that the smallest integer will contain atmost 2 digits.

EXPLANATION:

First we check if 0, 4 or 8 digits are present or not, if present the answer is simply mininum of three digits(consider those which are present). If all of them not present, then we will try to form a non-negative 2-digit number, which will be
a subsequence(as we are allowed remove digits) of the given number and print the smallest among them.If no 2-digit number can be formed then the answer is simply “NO”.

Since the number of test cases is atmost 10000, so we need to find this number in O(10 * number of digits) per query.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.