LeetCode 453 - Minimum Moves to Equal Array Elements


LeetCode - 462 Minimum Moves to Equal Array Elements II
https://leetcode.com/problems/minimum-moves-to-equal-array-elements/
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

https://discuss.leetcode.com/topic/66737/it-is-a-math-question
let's define sum as the sum of all the numbers, before any moves; minNum as the min number int the list; n is the length of the list;
After, say m moves, we get all the numbers as x , and we will get the following equation
 sum + m * (n - 1) = x * n
and actually,
  x = minNum + m
and finally, we will get
  sum - minNum * n = m
before all elements reach to the same value, every time (n-1) elements add one meaning only one element remains the same, which of cause should be the max value( should be different from min value, otherwise they have reached the same value) of the array. So, with that being said, every time doing add one for (n-1) operation, the min value +1. If it takes m moves to reach x, then x=minNum+m.

As long as min not equals to max, you keep doing add 1 to (n-1) elements, then min value for sure +1, I believe you understand this part already. So, I suppose your question is what if m moves means min value once equals to max and somehow this array adds 1 to (n-1) elements which makes it to go for another round to have all equal elements. If you think carefully, you will find out that by doing this, there exists a single add-1-operation that min value doesn't get to +1.
So, if you want to get the second minimum moves to reach to all equal state, then you can have these equations instead:(I am using OP's equations so I think you can better understand and compare the differences)
for second minimum m moves:
sum+m*(n-1)=x * n
x=minNum+m-1 (there is a single time min value doesn't +1)
sum-minNum * n+n=m (m gets n moves more compared to the minimum value, because it also means you need to decrease every element by 1 after it reaches to the first equality, easy to understand, right?)
Let me explain why x = minNum + m
our goal is :increment minNum to be equal to maxNum
  • No matter how many add operations are executed,the goal won't change.
  • Every time we do the add operation,the min number in the array must participate in.
  • After an add operation,the minNum is still the min number
    So the minNum participate in every add operation
    So x = minNum + m
https://discuss.leetcode.com/topic/66771/what-if-we-are-not-smart-enough-to-come-up-with-decrease-1-here-is-how-we-do-it/

https://discuss.leetcode.com/topic/66557/java-o-n-solution-short
Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.
So, best way to do this is make all the elements in the array equal to the min element.
sum(array) - n * minimum
    public int minMoves(int[] nums) {
        if (nums.length == 0) return 0;
        int min = nums[0];
        for (int n : nums) min = Math.min(min, n);
        int res = 0;
        for (int n : nums) res += n - min;
        return res;
    }
https://discuss.leetcode.com/topic/66562/simple-one-liners
public int minMoves(int[] nums) {
    return IntStream.of(nums).sum() - nums.length * IntStream.of(nums).min().getAsInt();
}
https://tech.liuchao.me/2016/11/leetcode-solution-453/
    public int minMoves(int[] nums) {
        int sum = 0, min = nums[0];
        for (int num : nums) {
            sum += num;
            min = Math.min(min, num);
        }
        return sum - nums.length * min;
    }
http://bookshadow.com/weblog/2016/11/06/leetcode-minimum-moves-to-equal-array-elements/
一次移动将n - 1个元素加1,等价于将剩下的1个元素减1。
因此累加数组中各元素与最小值之差即可。
def minMoves(self, nums): """ :type nums: List[int] :rtype: int """ return sum(nums) - min(nums) * len(nums)

https://discuss.leetcode.com/topic/66575/thinking-process-of-solving-problems-use-java-37ms
I try to find the max num every time, and +1 to rest num, code like below:
    public int minMoves(int[] nums) {
        return helper(nums, 0);
    }

    private int helper(int[] nums, int count) {
        int max = 0;
        int total = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[max]) max = i;
            else if (nums[i] == nums[max]) total++;
        }
        if (total == nums.length) return count;

        for (int i = 0; i < nums.length; i++) {
            if (i != max) nums[i]++;
        }
        return helper(nums, ++count);
    }
but when the nums is [1, 1, 2147483647], it will be java.lang.StackOverflowError.
So I try to improve in this way that find the max and min num every time, and +(max - min) to rest num, code like below:
    public int minMoves(int[] nums) {
        return helper(nums, 0);
    }

    private int helper(int[] nums, int count) {
        int max = 0, min = 0;
        int total = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[max]) max = i;
            else if (nums[i] < nums[min]) min = i;
            else if (nums[i] == nums[max]) total++;
        }
        if (total == nums.length) return count;

        int dis = nums[max] - nums[min];
        for (int i = 0; i < nums.length; i++) {
            if (i != max) nums[i] += dis;
        }
        return helper(nums, count + dis);
    }
But when the num length is bigger to 10000, it wil be Time Limit Exceeded.
Then, I want to implements it by no recursive way and use insert sort every time in order to reduce unnecessary traversal operation. code like below:
    public int minMoves(int[] nums) {
        int res = 0;
        int n = nums.length;
        Arrays.sort(nums);

        while (nums[n - 1] != nums[0]) {
            int dis = nums[n - 1] - nums[0];
            for (int i = 0; i < n - 1; i++) {
                nums[i] += dis;
            }
            res += dis;

            //insert sort
            int max = nums[n - 1];
            int i = n - 2;
            while (i >= 0) {
                if (nums[i] > max) nums[i + 1] = nums[i--];
                else break;
            }
            nums[i + 1] = max;
        }

        return res;
    }
But it still Time Limit Exceeded.
============== The final solution is as follows ==============
The final flash, I though that should we use dynamic programming?
  • [step] is The number of steps arrive at the state of [all equal]
  • [finalNum] is The value of the state of [all equal]
we can know that
  • step[i] = (step[i-1] + num[i]) - finalNum[i-1] + step[i-1]
  • finalNum[i] = num[i] + step[i-1]
    public int minMoves(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        int step = 0;
        int finalNum = nums[0];

        for (int i = 1; i < n; i++) {
            int tmp = finalNum;
            finalNum = nums[i] + step;
            if (finalNum == tmp) continue;   //attention!!
            step = finalNum - tmp + step;
        }

        return step;
    }


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts