Largest Multiple of Thirty
National Olympiad — National round (2026 season)
Submission name: guess.cpp
Problem summary
Rearrange all decimal digits of N to obtain the largest possible multiple of 30. If no arrangement is divisible by 30, output −1.
Input
One integer N, read conveniently as a string.
Output
The largest valid rearrangement, or −1 if none exists.
Constraints
0 ≤ N ≤ 1,000,000,000,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
3120
Output
3210
Solution analysis
- Divisibility by 30 means divisibility by both 10 and 3. Therefore at least one digit must be 0, and the digit sum must be divisible by 3.
- Digit rearrangement changes neither the digit multiset nor its sum. If either test fails, no permutation can work.
- Otherwise put the digits in decreasing order. This places a zero at the end and maximizes the first differing digit, so it gives the largest possible number. A frequency array prints this order without sorting.
- For 3120, the digit sum is 6 and a zero exists. Descending order gives 3210, which is divisible by 30. For N = 0, the correct output is 0.
Why it works
The two divisibility tests are necessary. When they pass, descending order ends in zero and has the same digit sum, so it is valid. Among all permutations, descending order is lexicographically and numerically largest; hence it is also the largest valid permutation.
Watch out. Use every digit, including zeros. Do not search all permutations. Read and output digits as text to avoid unnecessary numeric reconstruction. Handle the input 0 as a valid multiple.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main() {
string number;
cin >> number;
int frequency[10] = {};
int digitSum = 0;
for (char symbol : number) {
int digit = symbol - '0';
frequency[digit]++;
digitSum += digit;
}
if (frequency[0] == 0 || digitSum % 3 != 0) {
cout << "-1\n";
return 0;
}
// Descending digits maximize the value and leave a zero at the end.
for (int digit = 9; digit >= 0; digit--) {
for (int copy = 0; copy < frequency[digit]; copy++) {
cout << digit;
}
}
cout << '\n';
}