Problem Statement
A group of kids had N blank cards. Then, the following happened.
- Alice wrote a digit (0-9) onto each of the cards. At least one of the digits was non-zero.
- Bob arranged all N cards to form a valid non-negative integer. (The integer did not have any leading zeros.)
- Carol rearranged all N cards to form a valid non-negative integer. (Again, the integer did not have any leading zeros. Maybe it was the same integer as Bob's, maybe not.)
- Derek calculated the (non-negative) difference between Bob's and Carol's integer.
Calculate and return the largest value Derek could have obtained.
Definition
- Class:
- MaxDiffBetweenCards
- Method:
- solve
- Parameters:
- int
- Returns:
- long
- Method signature:
- long solve(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 17, inclusive.
Examples
1
Returns: 0
With just one card Bob and Carol both have to produce the same number, and Derek's difference will be zero.2
Returns: 72
The biggest difference is produced if Alice writes the digits 9 and 1, and Bob and Carol arrange them to form the numbers 91 and 19, respectively.4
Returns: 8811
Remember that some of the digits written by Alice may be zeros. The only requirement for her is that at least one of the digits must be non-zero. (This makes sure that Bob and Carol can always produce a valid integer.)