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.)
3
Returns: 801
5
Returns: 89001
6
Returns: 898101
7
Returns: 8990001
8
Returns: 89981001
9
Returns: 899900001
10
Returns: 8999810001
11
Returns: 89999000001
12
Returns: 899998100001
13
Returns: 8999990000001
14
Returns: 89999981000001
15
Returns: 899999900000001
16
Returns: 8999999810000001
17
Returns: 89999999000000001