Monday, November 7, 2016

LeetCode 453 - Minimum Moves to Equal Array Elements


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;
    }



No comments:

Post a Comment

Labels

GeeksforGeeks (1023) Algorithm (811) LeetCode (702) to-do (601) Review (415) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (269) LeetCode - Review (250) Google Interview (234) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (114) Cracking Coding Interview (110) Smart Algorithm (110) Math (95) HackerRank (88) Lintcode (83) Binary Search (75) Graph Algorithm (75) Greedy Algorithm (61) Interview Corner (61) Binary Tree (59) DFS (58) List (58) Codility (54) Algorithm Interview (53) Advanced Data Structure (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Knapsack (39) Stack (39) Binary Search Tree (38) Interval (38) Recursive Algorithm (38) String Algorithm (38) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Space Optimization (36) Beauty of Programming (35) Sort (35) Trie (34) Array (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) Binary Indexed Trees (21) DFS + Review (21) Pre-Sort (21) TopCoder (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Company-Facebook (19) UVA (19) Follow Up (18) Merge Sort (18) Probabilities (18) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Bisection Method (15) Iterator (15) O(N) (15) Post-Order Traverse (15) Priority Quieue (15) Difficult (14) Number (14) Number Theory (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) Ordered Stack (13) mitbbs (13) Combination (12) Computational Geometry (12) Euclidean GCD (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) Binary Search - Bisection (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Company - Microsoft (10) Company-Airbnb (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Time Complexity (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) O(1) Space (8) Prefix Sum (8) Prime (8) Quick Sort (8) Suffix Tree (8) System Design (8) Tech-Queries (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Minimum Spanning Tree (7) Miscs (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+Cache (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Inversion (6) Kadane - Extended (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary String (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts