The main observation here is that moving chips from position p to p+2 or p-2 incurs no cost. Hence, the cost to align all chips into one position is essentially the cost of moving all odd-indexed chips to even positions or vice versa.
To achieve this, count the number of chips at odd positions and the number of chips at even positions. The minimum cost to move all chips to the same position is the lesser of the two counts.
Time Complexity: O(n), where n is the number of chips.
Space Complexity: O(1) because only a fixed amount of extra space is used.
1#include <stdio.h>
2
3int minCostToMoveChips(int* position, int positionSize) {
4 int oddCount = 0, evenCount = 0;
5 for (int i = 0; i < positionSize; i++) {
6 if (position[i] % 2 == 0) evenCount++;
7 else oddCount++;
8 }
9 return oddCount < evenCount ? oddCount : evenCount;
10}
11
12int main() {
13 int position[] = {1, 2, 3};
14 int size = sizeof(position) / sizeof(position[0]);
15 printf("%d\n", minCostToMoveChips(position, size));
16 return 0;
17}This C solution iterates through each chip position and counts how many are at odd and even positions. The minimum of these two counts determines the cost to align all chips.
A similar but slightly varied approach leverages modular arithmetic to classify indices. As the cost is incurred when moving by an odd number of steps, the strategy remains to count parity of indices and work from there.
Time Complexity: O(n) for iterating through the list of positions.
Space Complexity: O(1), with fixed space used to track counts.
1import java.util.List;
2
3public class Solution {
4 public int minCostToMoveChips(List<Integer> position) {
5 int[] count = new int[2];
6 for (int pos : position) {
7 count[pos % 2]++;
8 }
9 return Math.min(count[0], count[1]);
10 }
11
12 public static void main(String[] args) {
13 Solution sol = new Solution();
14 List<Integer> position = Arrays.asList(1, 2, 3);
15 System.out.println(sol.minCostToMoveChips(position));
16 }
17}The solution applies Java's array structure to accumulate counts of even and odd indices, then utilizes Math.min to fetch the optimal cost to align sorts.