[Question of the day] 1217 playing chips

Leave a Comment / / wlnxing

Original link: https://wlnxing.com/archives/70.html

topic

There are n chips. The position of the i-th chip is position[i] .

We need to move all the chips to the same position. In one step, we can change the position of the i-th chip from position[i] to:

  • position[i] + 2 or position[i] – 2, then cost = 0
  • position[i] + 1 or position[i] – 1, then cost = 1
    Returns the minimum cost required to move all chips to the same position.

io

输入：position = [1,2,3]输出：1解释：第一步:将位置3的筹码移动到位置1，成本为0。第二步:将位置2的筹码移动到位置1，成本= 1。总成本是1。
输入：position = [2,2,2,3,3]输出：2解释：我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。
输入：position = [1,1000000000]输出：1

hint

  • 1 <= chips.length <= 100
  • 1 <= chips[i] <= 10^9

code

The idea of ​​moving an odd number of positions consumes 1 and an even number of positions consumes 0. In other words, even to even does not consume odd to odd, only odd to even and even to odd will consume 1. Then we can directly count the number of odd and even numbers , and finally returns the smallest

Just write:

 /** * @param {number[]} position * @return {number} */ var minCostToMoveChips = function(position) { let odd=0; let even=0; position.forEach(v=>{ if(v%2) odd++; else even++; }) return odd>even?even:odd }; console.log(minCostToMoveChips([2,2,2,3,3]))

submit:

This is a simple question, so try to optimize it:

  1. Use bitwise & instead of modulo
  2. Only remember one value (example for odd numbers), greatly reduce the number of ++, and finally judge the even number by subtracting the odd number from the length to be an even number
 /** * @param {number[]} position * @return {number} */ var minCostToMoveChips = function(position) { let odd=0; position.forEach(v=>{ if(v & 1) odd++; }) return odd>position.length-odd?position.length-odd:odd };

submit:

bingo! nice!

This article is reprinted from: https://wlnxing.com/archives/70.html
This site is for inclusion only, and the copyright belongs to the original author.

Leave a Comment