nums = [1, 2, 3]

3

nums = [1, 1, 1]

0

moves = ∑ᵢ₌₀ⁿ⁻¹ (nums[i] - minVal)

def minMoves(nums):
    # Find the minimum value in the array.
    minVal = min(nums)
    # Compute the total number of moves required.
    moves = sum(num - minVal for num in nums)
    return moves

# Example usage:
nums = [1, 2, 3]
print(minMoves(nums))  # Output: 3

nums = [1, 2, 3]

Output:

2

Explanation:
Only two moves are needed (each move increments or decrements one element):

• Step 1: [1, 2, 3] => [2, 2, 3]

• Step 2: [2, 2, 3] => [2, 2, 2]

---

Example 2:

Input:

nums = [1, 10, 2, 9]

Output:

16

▎Constraints

•  n = nums.length 

•  1 ≤ n ≤ 10⁵ 

•  -10⁹ ≤ nums[i] ≤ 10⁹ 

▎Explanation

To minimize the number of moves, you want to choose a target value that minimizes the sum of the absolute differences between each element and that target. It can be proven that the best target value is the median of the array.

If the array is sorted, the median minimizes the sum of absolute deviations. Thus, the minimum number of moves is given by:

moves = ∑ᵢ₌₀ⁿ⁻¹ | nums[i] - median |

def minMoves2(nums):
    # Sort the array to find the median.
    nums.sort()
    n = len(nums)
    median = nums[n // 2]  # Get the median value
    
    # Compute the total moves as the sum of absolute differences.
    moves = sum(abs(num - median) for num in nums)
    return moves

# Example usage:
nums1 = [1, 2, 3]
print(minMoves2(nums1))  # Output: 2

nums2 = [1, 10, 2, 9]
print(minMoves2(nums2))  # Output: 16

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxReach = 0
        for i, jump in enumerate(nums):
            if i > maxReach:
                return False
            maxReach = max(maxReach, i + jump)
            if maxReach >= len(nums) - 1:
                return True
        return False

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last = len(nums)-1
        for i in range(len(nums)-2,-1,-1):
            if nums[i]+i >= last:
                last = i
        return nums[0] >= last

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        count = 0
        while target>1 and maxDoubles>0:
            if target%2:
                count+=1
            target = target//2
            maxDoubles-=1
            count += 1
        count += target -1
        return count

▎976. Largest Perimeter Triangle

Difficulty: Easy

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

▎Example 1:

Input: 

nums = [2, 1, 2]

Output: 

5

Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

▎Example 2:

Input: 

nums = [1, 2, 1, 10]

Output: 

0

Explanation:

• You cannot use the side lengths 1, 1, and 2 to form a triangle.

• You cannot use the side lengths 1, 1, and 10 to form a triangle.

• You cannot use the side lengths 1, 2, and 10 to form a triangle.

As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

▎Approach

To solve this problem, we can follow these steps:

1. Sort the Array: Start by sorting the array in non-decreasing order.

2. Check Triplets: Iterate through the sorted array from the end to the beginning and check for valid triplets that can form a triangle using the Triangle Inequality Theorem.

3. Return the Perimeter: If a valid triplet is found, calculate and return their perimeter. If no valid triplet is found, return 0.

▎Implementation

Here’s a Python implementation of the approach:

def largestPerimeter(nums):
    # Sort the array in non-decreasing order
    nums.sort()
    
    # Iterate from the end of the sorted list to find a valid triangle
    for i in range(len(nums) - 1, 1, -1):
        # Check if nums[i-2], nums[i-1], nums[i] can form a triangle
        if nums[i - 2] + nums[i - 1] > nums[i]:
            # If they can, return their perimeter
            return nums[i - 2] + nums[i - 1] + nums[i]
    
    # If no valid triangle is found, return 0
    return 0

# Example usage:
print(largestPerimeter([2, 1, 2]))  # Output: 5
print(largestPerimeter([1, 2, 1, 10]))  # Output: 0

▎Conclusion

This solution efficiently finds the largest perimeter of a triangle that can be formed from three lengths in the given array. If no such triangle exists, it correctly returns 0.

Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation:
- From the first 3 customers, we collect three $5 bills.
- From the fourth customer, we collect a $10 bill and give back a $5.
- From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation:
- From the first two customers, we collect two $5 bills.
- For the next two customers, we collect a $10 bill and give back a $5 bill.
- For the last customer, we cannot give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

▎Constraints

• 1 ≤ bills.length ≤ 10⁵

• bills[i] is either 5, 10, or 20.

▎Solution Code

from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        c5 = 0  # Count of $5 bills
        c10 = 0 # Count of $10 bills
        
        for i in bills:
            if i == 5:
                c5 += 1
            elif i == 10:
                c10 += 1
                c5 -= 1
            else: # i == 20
                if c10 > 0:
                    c10 -= 1
                    c5 -= 1
                else:
                    c5 -= 3
            
            # Check if we have enough $5 bills to give change
            if c5 < 0:
                return False
        
        return True

Input: nums = [3, 9, 3]
Output: 2
Explanation:
- Operation 1: Replace 9 with [3, 6] → Array becomes [3, 3, 6, 3]
- Operation 2: Replace 6 with [3, 3] → Array becomes [3, 3, 3, 3, 3]
Thus, a total of 2 operations are required.

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation: 
The array is already in non-decreasing order. Therefore, no operations are needed.

▎Constraints

• 1 ≤ nums.length ≤ 10⁵

• 1 ≤ nums[i] ≤ 10⁹

▎Solution Code

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        operations = 0
        n = len(nums)
        
        # Start from the second last element and move backward
        for i in range(n - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                # Calculate how many parts we need to break nums[i] into
                parts = (nums[i] + nums[i + 1] - 1) // nums[i + 1]
                operations += parts - 1
                
                # Set nums[i] to the maximum value allowed
                nums[i] = nums[i] // parts
        
        return operations