FilesExpand file tree

 master

/

MinimumMovesToEqualArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (64 loc) · 1.81 KB

 master

/

MinimumMovesToEqualArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (64 loc) · 1.81 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

package array;

import java.util.Arrays;

/**

* Created by gouthamvidyapradhan on 17/02/2018. Given a non-empty integer array, find the minimum

* number of moves required to make all array elements equal, where a move is incrementing a

* selected element by 1 or decrementing a selected element by 1.

*

* <p>You may assume the array's length is at most 10,000.

*

* <p>Example:

*

* <p>Input: [1,2,3]

*

* <p>Output: 2

*

* <p>Explanation: Only two moves are needed (remember each move increments or decrements one

* element):

*

* <p>[1,2,3] => [2,2,3] => [2,2,2]

*

* <p>Solution: O(n log n): Sort the array and find the median of the array. Use the median of array

* to increment/decrement other value of array. Sum up the difference and return the answer.

*/

public class MinimumMovesToEqualArray {

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

int[] A = {1, 2, 3};

System.out.println(new MinimumMovesToEqualArray().minMoves2(A));

}

public int minMoves2(int[] nums) {

if (nums.length == 1) return 0;

else if (nums.length == 2) return Math.abs(nums[0] - nums[1]);

Arrays.sort(nums);

int median;

if ((nums.length % 2) == 1) {

median = (nums.length / 2);

int sum = 0;

for (int i = 0; i < nums.length; i++) {

sum += Math.abs(nums[i] - nums[median]);

}

return sum;

} else {

median = (nums.length / 2) - 1;

int sum = 0;

int min;

for (int i = 0; i < nums.length; i++) {

sum += Math.abs(nums[i] - nums[median]);

}

min = sum;

sum = 0;

median = (nums.length / 2);

for (int i = 0; i < nums.length; i++) {

sum += Math.abs(nums[i] - nums[median]);

}

min = Math.min(min, sum);

return min;

}

}

}