Problem Statement
Bob had an array that contained the integers from 1 to N, inclusive. He converted each integer into a string. Then, he sorted the array. Finally, he converted each string back into an integer.
Count and return the number of inversions in Bob's final array.
Definition
- Class:
- SortInversions
- Method:
- count
- Parameters:
- int
- Returns:
- long
- Method signature:
- long count(int N)
- (be sure your method is public)
Notes
- A pair of indices (i, j) into an array B is an inversion if and only if (i < j and B[i] > B[j]). In other words, an inversion is a pair of elements such that the bigger element is to the left of the smaller one.
Constraints
- N will be between 1 and 10^9, inclusive.
Examples
12
Returns: 24
Bob had the array {1, 2, ..., 9, 10, 11, 12}. He converted the elements to strings: {"1", "2", ..., "9", "10", "11", "12"}. He sorted those strings: {"1", "10", "11", "12", "2", ..., "9"}. He converted everything back to integers: {1, 10, 11, 12, 2, ..., 9}. This array now contains 24 inversions.7
Returns: 0
199
Returns: 9610
999999
Returns: 45451601010