cx9
BAN USERYes, Veeru you are right. There is logical incorrectness in my algo. This statement in my first reply "suppose the largest element is inserted to position i. elements behind it increase the distance by 1elements behind it increase the distance by 1" doesn't hold. It's easy to give a counter example. So my algo is a wrong one.
- cx9 September 28, 2012Maybe you don't understand what I mean.
In your example: {3, 5, 7, 2, 8}
The positions of elements are:
p(3) = 1, p(5) = 2, p(7) = 3, p(2) = 4, p(8) = 5;
in the sorted array {2, 3, 5, 7, 8}
p'(2) = 1, p'(3) = 2, p'(5) = 3, p'(7) = 4, p'(8) = 5;
And the distance I talked about is such as:
|p(3)-p'(3)| = |1-2| = 1.
So the sum is |1-2| + |2-3| + |3-4| + |4-1| + |5-5| = 6;
Output is 6/2 = 3.
My algo needs O(n) extra space.
Convert the number to its octal notation, and sum up the digits. The sum is multiple of 7 if and only if the original number is.
- cx9 October 02, 2012