Last Stone Weight

🏠 ⬅️ ➡️

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1] Output: 1

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n_examples = 2
    integer, parameter :: stones(n_examples) = reshape([2, 7, 4, 1, 8, 1], shape=[n_examples])
    integer :: i

    do i = 1, n_examples
        print '(A, I0)', 'Example ', i
        print '(A, I0)', 'Stones: ', stones(i)
        print '(A, I0)', 'Result: ', solve(stones(i))
        print *, ''
    end do

contains

    function solve(stones) result(result)
        implicit none
        integer, intent(in) :: stones(:)
        integer :: result, x, y

        if (size(stones) == 1) then
            result = stones(1)
        else
            x = maxval(stones)
            y = minval(stones)
            if (x == y) then
                result = 0
            else
                if (x < y) then
                    result = y - x
                else
                    result = x
                end if
            end if
        end if
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module smashing_stones
implicit none
contains

function smashing_stones(stones) result(last_stone)
integer, intent(in) :: stones(:)
integer :: last_stone, i, j, x, y

! Sort the stones in descending order
call sort(stones)

! Initialize the last stone
last_stone = stones(1)

! Loop through the stones and smash the heaviest two
do i = 2, size(stones)
    x = stones(i - 1)
    y = stones(i)

    ! If x == y, both stones are destroyed
    if (x == y) then
        last_stone = 0
        exit
    ! If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x
    else
        last_stone = y - x
    end if
end do

end function smashing_stones

end module smashing_stones

program test_smashing_stones
use smashing_stones
implicit none
integer :: stones(6)

! Test case 1
stones = [2, 7, 4, 1, 8, 1]
write (*,*) 'Test case 1:', smashing_stones(stones)

! Test case 2
stones = [1]
write (*,*) 'Test case 2:', smashing_stones(stones)

! Test case 3
stones = [2, 1, 1, 1, 1, 1]
write (*,*) 'Test case 3:', smashing_stones(stones)

! Test case 4
stones = [2, 7, 4, 1, 8, 1, 2]
write (*,*) 'Test case 4:', smashing_stones(stones)

! Test case 5
stones = [2, 1, 1, 1, 1, 1, 2]
write (*,*) 'Test case 5:', smashing_stones(stones)

end program test_smashing_stones
🌐 Data from online sources 
def longestOnes(nums, k):
    left, right, max_ones, zero_count = 0, 0, 0, 0
    while right < len(nums):
        if nums[right] == 0:
            zero_count += 1
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        max_ones = max(max_ones, right - left + 1)
        right += 1
    return max_ones

The algorithm for this problem is a sliding window solution. We iterate through the array, and for each iteration, we check if the current element is a 0. If it is, we increment the zeroCount. If the zeroCount exceeds k, we move the left pointer of the sliding window forwards, checking if the element we are leaving is a 0, and decrementing the zeroCount accordingly. We then calculate and store the maximum consecutive 1's within the sliding window for each iteration, incrementing the right pointer of the sliding window at every step. Finally, we return the maximum consecutive 1's after iterating through the whole array. The algorithm focuses on processing the array in a single pass and adjusting window boundaries accordingly. Each language implementation follows this algorithm and uses similar variable names for convenience.
🌐 Data from online sources 
int longestOnes(vector<int>& nums, int k) {
    int left = 0, right = 0, maxOnes = 0, zeroCount = 0;
    while (right < nums.size()) {
        if (nums[right] == 0) zeroCount++;
        while (zeroCount > k) {
            if (nums[left] == 0) zeroCount--;
            left++;
        }
        maxOnes = max(maxOnes, right - left + 1);
        right++;
    }
    return maxOnes;
}

The algorithm for this problem is a sliding window solution. We iterate through the array, and for each iteration, we check if the current element is a 0. If it is, we increment the zeroCount. If the zeroCount exceeds k, we move the left pointer of the sliding window forwards, checking if the element we are leaving is a 0, and decrementing the zeroCount accordingly. We then calculate and store the maximum consecutive 1's within the sliding window for each iteration, incrementing the right pointer of the sliding window at every step. Finally, we return the maximum consecutive 1's after iterating through the whole array. The algorithm focuses on processing the array in a single pass and adjusting window boundaries accordingly. Each language implementation follows this algorithm and uses similar variable names for convenience.