Find Closest Number to Zero

🏠 ⬅️ ➡️

Given an integer array nums of size n, return the number with the value closest to 0 in nums. If there are multiple answers, return the number with the largest value.

Example 1:

Input: nums = [-4,-2,1,4,8] Output: 1 Explanation: The distance from -4 to 0 is |-4| = 4. The distance from -2 to 0 is |-2| = 2. The distance from 1 to 0 is |1| = 1. The distance from 4 to 0 is |4| = 4. The distance from 8 to 0 is |8| = 8. Thus, the closest number to 0 in the array is 1.

Example 2:

Input: nums = [2,-1,1] Output: 1 Explanation: 1 and -1 are both the closest numbers to 0, so 1 being larger is returned.

Constraints:

  • 1 <= n <= 1000
  • -105 <= nums[i] <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solve the problem: Given an integer array `nums` of size `n`, return the number with the value closest to 0 in `nums`. If there are multiple answers, return the number with the largest value.
    implicit none
    integer, parameter :: n = 5
    integer, dimension(n) :: nums
    integer :: i

    nums = [-4, -2, 1, 4, 8]
    call solve(nums)

    nums = [2, -1, 1]
    call solve(nums)

contains

    subroutine solve(nums)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer :: closest, largest
        integer :: i

        closest = nums(1)
        largest = nums(1)

        do i = 2, size(nums)
            if (abs(nums(i)) < abs(closest)) then
                closest = nums(i)
            end if
            if (abs(nums(i)) > abs(largest)) then
                largest = nums(i)
            end if
        end do

        print '(I0)', closest
        print '(I0)', largest
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module closest_number

contains

  function closest_number(nums) result(closest)
    implicit none
    integer, intent(in) :: nums(:)
    integer :: closest, i, j, diff, min_diff
    logical :: found

    ! Initialize closest to the first element
    closest = nums(1)

    ! Loop through the array and find the closest number to 0
    do i = 2, size(nums)
      diff = abs(nums(i) - 0)
      if (diff < min_diff .or. min_diff == -1) then
        closest = nums(i)
        min_diff = diff
      end if
    end do

    ! If there are multiple closest numbers, return the one with the largest value
    if (min_diff == 0) then
      do i = 1, size(nums)
        if (nums(i) == closest) then
          found = .true.
          exit
        end if
      end do
      if (.not. found) then
        do i = 1, size(nums)
          if (nums(i) > closest) then
            closest = nums(i)
          end if
        end do
      end if
    end if

  end function closest_number

end module closest_number

program test_closest_number
  use closest_number
  implicit none
  integer, parameter :: n = 5
  integer :: nums(n) = [ -4, -2, 1, 4, 8 ]
  integer :: closest

  closest = closest_number(nums)
  write (*,*) 'Closest number to 0 in nums:', closest

  nums = [ 2, -1, 1 ]
  closest = closest_number(nums)
  write (*,*) 'Closest number to 0 in nums:', closest

  nums = [ 1, 2, 3, 4, 5 ]
  closest = closest_number(nums)
  write (*,*) 'Closest number to 0 in nums:', closest

  nums = [ -1, -2, -3, -4, -5 ]
  closest = closest_number(nums)
  write (*,*) 'Closest number to 0 in nums:', closest

end program test_closest_number
🌐 Data from online sources 
def robot_instructions(n: int, start_pos: list, s: str) -> list:
    answer = [0] * len(s)

    for idx in range(len(s)):
        row, col = start_pos

        for i in range(idx, len(s)):
            move = s[i]
            if move == 'L':
                col -= 1
            elif move == 'R':
                col += 1
            elif move == 'U':
                row -= 1
            elif move == 'D':
                row += 1

            if row < 0 or row >= n or col < 0 or col >= n:
                break

            answer[idx] += 1

    return answer

This algorithm implements a nested loop. The outer loop iterates through each starting instruction index. In the inner loop, we execute the instructions while updating the position of the robot in terms of row and column. If a move will take the robot outside the grid, we break from the inner loop. If the robot hasn't exited the grid, we increase the number of instructions it has executed, which is stored in the answer array indexed by the starting instruction index.

The time complexity is O(m^2), where m is the length of the instructions string s. The space complexity is O(m), as we need to store the answer for each starting instruction index in an array.

🌐 Data from online sources 
#include <vector>
#include <string>

std::vector<int> robotInstructions(int n, std::vector<int>& startPos, const std::string& s) {
    std::vector<int> answer(s.length(), 0);

    for (int idx = 0; idx < s.length(); ++idx) {
        int row = startPos[0];
        int col = startPos[1];

        for (int i = idx; i < s.length(); ++i) {
            if (s[i] == 'L') --col;
            else if (s[i] == 'R') ++col;
            else if (s[i] == 'U') --row;
            else if (s[i] == 'D') ++row;

            if (row < 0 || row >= n || col < 0 || col >= n) {
                break;
            }

            answer[idx]++;
        }
    }

    return answer;
}

This algorithm implements a nested loop. The outer loop iterates through each starting instruction index. In the inner loop, we execute the instructions while updating the position of the robot in terms of row and column. If a move will take the robot outside the grid, we break from the inner loop. If the robot hasn't exited the grid, we increase the number of instructions it has executed, which is stored in the answer array indexed by the starting instruction index.

The time complexity is O(m^2), where m is the length of the instructions string s. The space complexity is O(m), as we need to store the answer for each starting instruction index in an array.