Minumum Cost to Move Chips to the Same Position — LeetCode
Here is the problem:
This problem stumped me at first. I first thought that each index was a token holder and the number represented the number of tokens at that index. I was trying to solve this way for a long time. Eventually, I started reading the discussion section of the problem and figured it out.
Here is my code that solves the problem:
The most important thing to realize for this problem is that it’s free (no cost) to move a chip from an odd index to another odd index. You only have to increment the cost when you move a chip from an odd index to an even index, and vice versa.
With that in mind, we can iterate through all of the chips, and check if it’s even or odd. If it’s even, we do even_parity += 1, and if it’s odd, we do odd_parity += 1. After we have those numbers, we want to return the smallest number.
“All chips must be in the same position once we’re done, which is either even or odd. Therefore, we want to calculate whether it is cheaper to move all the odd chips to even or all the even chips to odd. This will simply come down to how many even chips we start with, and how many odd chips. Each chip that has to be moved will cost exactly 1” (Explanation referenced from here).
Here’s the submission report for the above code:
