Minimum Cost to Move Chips to The Same Position

šŸ  ā¬…ļø āž”ļø

We have n chips, where the position of the ith 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 ith chip from position[i] to:

  • position[i] + 2 or position[i] - 2 with cost = 0.
  • position[i] + 1 or position[i] - 1 with cost = 1.

Return the minimum cost needed to move all the chips to the same position.

Example 1:

Input: position = [1,2,3] Output: 1 Explanation: First step: Move the chip at position 3 to position 1 with cost = 0. Second step: Move the chip at position 2 to position 1 with cost = 1. Total cost is 1.

Example 2:

Input: position = [2,2,2,3,3] Output: 2 Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.

Example 3:

Input: position = [1,1000000000] Output: 1

Constraints:

  • 1 <= position.length <= 100
  • 1 <= position[i] <= 10^9
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, dimension(n) :: position = (/ 1, 2, 3 /)
    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
    integer :: cost
    integer :: minCost

    ! Example 1
    write (*,*) "Example 1:"
    write (*,*) "position = ", position
    cost = 0
    call moveChips(position, cost)
    write (*,*) "minCost = ", minCost

    ! Example 2
    write (*,*) "Example 2:"
    write (*,*) "position = ", position
    cost = 0
    call moveChips(position, cost)
    write (*,*) "minCost = ", minCost

    ! Example 3
    write (*,*) "Example 3:"
    write (*,*) "position = ", position
    cost = 0
    call moveChips(position, cost)
    write (*,*) "minCost = ", minCost

contains

    subroutine moveChips(position, cost)
        implicit none
        integer, intent(inout) :: position(:)
        integer, intent(inout) :: cost
        integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

        do i = 1, size(position)
            if (position(i) == position(i+1)) then
                cost = cost + 1
            else if (position(i) == position(i+1)+1 .or. position(i) == position(i+1)-1) then
                cost = cost + 2
            end if
        end do

        minCost = cost
    end subroutine moveChips

end program main
āœ… Compiled
āœ… Executed
āŒ Correct 
module chips
implicit none
contains

function min_cost(position) result(cost)
integer, intent(in) :: position(:)
integer :: cost, i, j, diff

! Initialize the cost to 0
cost = 0

! Loop through each chip
do i = 1, size(position)

    ! Loop through each chip again
    do j = 1, size(position)

        ! If the current chip is not the same as the current chip,
        ! calculate the difference between their positions
        if (i /= j) then
            diff = abs(position(i) - position(j))

            ! If the difference is 1, the cost is 1
            if (diff == 1) then
                cost = cost + 1
            ! If the difference is 2, the cost is 0
            else if (diff == 2) then
                cost = cost + 0
            end if
        end if
    end do
end do

end function min_cost
end module chips

program main
use chips
implicit none
integer, parameter :: n = 3
integer :: position(n) = [1, 2, 3]
integer :: cost

! Call the min_cost function and store the result in cost
cost = min_cost(position)

! Print the cost to stdout
write (*,*) cost

end program main
šŸŒ Data from online sources 
def sort_array(arr1, arr2):
    counts = {}
    result = []

    for num in arr1:
        counts[num] = counts.get(num, 0) + 1

    for num in arr2:
        if num in counts:
            result.extend([num] * counts[num])
            del counts[num]

    for num in sorted(counts.keys()):
        result.extend([num] * counts[num])

    return result
  1. Create a dictionary counts to store the count of each number in arr1.
  2. Iterate through the elements of arr2. For each element, add that element to the result n times where n is the count of that element in arr1. Remove the element from the counts dictionary.
  3. Iterate through the sorted keys of the remaining elements in counts. For each key, append the key to the result n times where n is the count of that element in arr1.
  4. Return the resulting sorted array.
šŸŒ Data from online sources 
#include <vector>
#include <map>
#include <algorithm>

void sortArray(vector<int>& arr1, vector<int>& arr2) {
    map<int, int> counts;

    for (int num : arr1) {
        counts[num]++;
    }
    int index = 0;
    for (int num : arr2) {
        while (counts[num]--) {
            arr1[index++] = num;
        }
    }
    for (auto &pair : counts) {
        while (pair.second--) {
            arr1[index++] = pair.first;
        }
    }
}
  1. Create a dictionary counts to store the count of each number in arr1.
  2. Iterate through the elements of arr2. For each element, add that element to the result n times where n is the count of that element in arr1. Remove the element from the counts dictionary.
  3. Iterate through the sorted keys of the remaining elements in counts. For each key, append the key to the result n times where n is the count of that element in arr1.
  4. Return the resulting sorted array.