PROBLEM LINK:
Author: Divyesh Savaliya
Editorialist: Divyesh Savaliya
DIFFICULTY:
Medium - Hard
PREREQUISITES:
Math, Hashing
PROBLEM:
You are given N single digit numbers. Form a number with the given N digit in such a way that the newly formed number should be completely divisible by 5 and 6 i.e 30. And the formed number from these digits should be maximum.
EXPLANATION:
The number is divisible by 30 iff it contains at least one 0 AND the sum of digits is divisible by 3. So, there are two answer.
- If 0 is not present in given N digits, then the answer is simply -1.
- If 0 is present, then select the digits whose sum is divisible by 3 and the number form by those digits is maximum.
First is easy, just check the input and print. To solve the second case, use the property of modulo and 3.The remainder is 0 or 1 or 2 if we divide any number by 3. So, we can use this property.
Now, make three bucket (number it: 0,1,2) as follow:
- Bucket 0 contains all numbers whose modulo with 3 is 0.
- Bucket 1 contains all numbers whose modulo with 3 is 1.
- Bucket 2 contains all numbers whose modulo with 3 is 2.
In order to make the number maximum, the length of formed number should be as maximum as possible. So, the newly formed number must contains all the digits present in bucket 0. Becausue the sum of that digits are divisible by 3. Now, we may need to remove some number either from bucket 1 or bucket 2.
There are three situation:
-
If the sum of all digits given in input modulo 3 is 0, select all digits.
-
If the sum of all digits given in input modulo 3 is 1, remove minimum digit present in bucket 1 if bucket 1 is not empty. If bucket 1 is empty, remove first two minimum digits from bucket 2.
-
If the sum of all digits given in input modulo 3 is 2, remove minimum digit present in bucket 2 if bucket 2 is not empty. If bucket 2 is empty, remove first two minimum digits from bucket 1.
First is simple. Second is little bit tricky, so we will try to understand it in two part.
-
If bucket is not empty.
Sum of all digits modulo 3 comes out as 1. It means that if we divide the sum of all digits by 3, the remainder is 1.
This provide a clue to solve problem
If we subtract 1 from the sum, then the sum is completely divisible by 3. Now, according to modular arithmetic property, to make the sum divisible by 3, we can subtract any digit from sum whose modulo 3 turns out as 1.
E.g. (sum - b) % 3 = (sum%3 - b%3) % 3 = 0.Here b is any digit whose modulo 3 is 1. Since sum%3 is 1 and b%3 is also 1, so (1-1) = 0. Hence, (sum - b) is divisible by 3.
So, to make the output number maximum and divisible by 3, remove minimum number from bucket 1. -
If bucket is empty.
Since the bucket is empty and sum is 1, we must need to subtract such number whose modulo 3 turns out as 1. So, the sum of two digits present in bucket 2 modulo 3 turns out as 1. Why and how only two digits? See below example.
E.g. (sum - n*c) % 3 = (sum%3 - ( (n%3)*(c%3) ) % 3) % 3 = 0.Here n is number of digit required. And in order to make this zero, n must be 2. Because 2%3 is 2 and c%3 is also 2 ( c is selected from bucket 2 ). So, (2*2)%3 turns out as 1 which we require. So, ( (sum%3 = 1) - 1 ) become 0.`
Similar procedure and explanation is for situation three.
Now after removing required minimum digits, to make the output number maximum, merge all bucket in one bucket. And then sort the new one bucket in non-increasing order and print it.
Time Complexity is O(n log n).
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.