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
1
Returns: 0
10
Returns: 8
17
Returns: 64
47
Returns: 250
98
Returns: 360
99
Returns: 360
100
Returns: 457
1000000000
Returns: 45454542010101000
986765889
Returns: 45444810963558720
997987989
Returns: 45454316117225460
909876567
Returns: 45003306204116886
899999999
Returns: 44898985860101010
888888888
Returns: 44768670401047512
800000000
Returns: 43232319632323224
777000000
Returns: 42691819722378781
777000777
Returns: 42691838974674326
967876654
Returns: 45397212833254550
76543210
Returns: 423977313421975
7457453
Returns: 4186286830268
46467
Returns: 295218548
5757
Returns: 3533570
498756453
Returns: 31496482464133056
999999
Returns: 45451601010
1000
Returns: 45006