There are some chips, and the i-th chip is at position chips[i]
.
You can perform any of the two following types of moves any number of times (possibly zero) on any chip:
- Move the
i
-th chip by 2 units to the left or to the right with a cost of 0. - Move the
i
-th chip by 1 unit to the left or to the right with a cost of 1.
There can be two or more chips at the same position initially.
Return the minimum cost needed to move all the chips to the same position (any position).
Example 1:
Input: chips = [1,2,3] Output: 1 Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.
Example 2:
Input: chips = [2,2,2,3,3] Output: 2 Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.
Constraints:
1 <= chips.length <= 100
1 <= chips[i] <= 10^9
Solution: Math
We can choose either:
1. move all odd positions to an arbitrary even position and move the rest to the same position
2. move all even positions to an arbitrary odd position and move the rest to the same position
ans = min(# of odd pos, # of even pos)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int minCostToMoveChips(vector<int>& chips) { int odd = 0; int even = 0; for (int p : chips) { if (p % 2) { ++odd; } else { ++even; } } return min(odd, even); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment