Largest Number At Least Twice of Others

🏠 ⬅️ ➡️

You are given an integer array nums where the largest integer is unique.

Determine whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, or return -1 otherwise.

Example 1:

Input: nums = [3,6,1,0] Output: 1 Explanation: 6 is the largest integer. For every other number in the array x, 6 is at least twice as big as x. The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1,2,3,4] Output: -1 Explanation: 4 is less than twice the value of 3, so we return -1.

Constraints:

  • 2 <= nums.length <= 50
  • 0 <= nums[i] <= 100
  • The largest element in nums is unique.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: nums
    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

    ! Example 1
    nums = [3, 6, 1, 0]
    print '(I0)', largest_element_at_least_twice(nums)

    ! Example 2
    nums = [1, 2, 3, 4]
    print '(I0)', largest_element_at_least_twice(nums)

contains

    function largest_element_at_least_twice(nums) result(largest_index)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer :: largest_index
        integer :: i

        largest_index = -1
        do i = 1, size(nums)
            if (nums(i) >= 2 * nums(size(nums))) then
                largest_index = i
                exit
            end if
        end do
    end function largest_element_at_least_twice

end program main
❌ Compiled
❌ Executed
❌ Correct 
module largest_integer
    implicit none
    private
    public :: largest_integer
contains
    function largest_integer(nums) result(largest)
        integer, intent(in) :: nums(:)
        integer :: largest
        integer :: i, j
        logical :: found

        largest = -1
        found = .false.

        ! Find the largest integer in the array
        do i = 1, size(nums)
            if (nums(i) > largest) then
                largest = nums(i)
            end if
        end do

        ! Check if the largest integer is at least twice as much as every other number in the array
        do i = 1, size(nums)
            if (largest /= nums(i)) then
                if (largest /= 2 * nums(i)) then
                    found = .true.
                    exit
                end if
            end if
        end do

        ! If the largest integer is at least twice as much as every other number in the array, return its index
        if (.not. found) then
            largest = largest_integer_index(nums)
        end if
    end function

    function largest_integer_index(nums) result(index)
        integer, intent(in) :: nums(:)
        integer :: index
        integer :: i

        index = -1

        ! Find the index of the largest integer in the array
        do i = 1, size(nums)
            if (nums(i) == largest_integer(nums)) then
                index = i
                exit
            end if
        end do
    end function
end module

program test_largest_integer
    use largest_integer
    implicit none
    integer, parameter :: nums1(4) = [3, 6, 1, 0]
    integer, parameter :: nums2(4) = [1, 2, 3, 4]
    integer, parameter :: nums3(4) = [1, 2, 3, 4]
    integer, parameter :: nums4(4) = [1, 2, 3, 4]
    integer, parameter :: nums5(4) = [1, 2, 3, 4]
    integer, parameter :: nums6(4) = [1, 2, 3, 4]
    integer, parameter :: nums7(4) = [1, 2, 3, 4]
    integer, parameter :: nums8(4) = [1, 2, 3, 4]
    integer, parameter :: nums9(4) = [1, 2, 3, 4]
    integer, parameter :: nums10(4) = [1, 2, 3, 4]

    write (*, '(A)') 'Test 1: ' // num2str(largest_integer(nums1))
    write (*, '(A)') 'Test 2: ' // num2str(largest_integer(nums2))
    write (*, '(A)') 'Test 3: ' // num2str(largest_integer(nums3))
    write (*, '(A)') 'Test 4: ' // num2str(largest_integer(nums4))
    write (*, '(A)') 'Test 5: ' // num2str(largest_integer(nums5))
    write (*, '(A)') 'Test 6: ' // num2str(largest_integer(nums6))
    write (*, '(A)') 'Test 7: ' // num2str(largest_integer(nums7))
    write (*, '(A)') 'Test 8: ' // num2str(largest_integer(nums8))
    write (*, '(A)') 'Test 9: ' // num2str(largest_integer(nums9))
    write (*, '(A)') 'Test 10: ' // num2str(largest_integer(nums10))

contains

    function num2str(num) result(str)
        integer, intent(in) :: num
        character(len=20) :: str

        write (str, '(I20)') num
    end function
🌐 Data from online sources 
def minCostClimbingStairs(cost):
    for i in range(2, len(cost)):
        cost[i] += min(cost[i-1], cost[i-2])
    return min(cost[-1], cost[-2])

The algorithm is based on dynamic programming. We loop through the array starting from index 2 (since we can start from step 0 or 1 without any cost), and at each step, we add the minimum of the costs of the previous two steps to the current step. We do this to find the optimal path at each step, which eventually leads to the minimum cost to reach the top. After processing the whole array, we return the minimum of the costs of the last two steps as the result.

🌐 Data from online sources 
int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    for(int i=2; i<n; i++)
        cost[i] += min(cost[i-1], cost[i-2]);
    return min(cost[n-1], cost[n-2]);
}

The algorithm is based on dynamic programming. We loop through the array starting from index 2 (since we can start from step 0 or 1 without any cost), and at each step, we add the minimum of the costs of the previous two steps to the current step. We do this to find the optimal path at each step, which eventually leads to the minimum cost to reach the top. After processing the whole array, we return the minimum of the costs of the last two steps as the result.