Check If It Is a Straight Line

🏠 ⬅️ ➡️

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false

Constraints:

  • 2 <= coordinates.length <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates contains no duplicate point.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: dp = selected_real_kind(15)

    real(dp), allocatable :: coordinates(:, :)
    integer :: n, i, j
    logical :: is_straight

    ! read input
    read(*, *) n
    allocate(coordinates(n, 2))
    do i = 1, n
        read(*, *) coordinates(i, :)
    end do

    ! check if points make a straight line
    is_straight = .true.
    do i = 2, n
        do j = 1, i-1
            if (abs(coordinates(i, 1) - coordinates(j, 1)) > epsilon(1._dp)) then
                is_straight = .false.
                exit
            end if
        end do
        if (.not. is_straight) exit
    end do

    ! print result
    write(*, '(L1)') is_straight

end program main
❌ Compiled
❌ Executed
❌ Correct 
module straight_line
  implicit none
  private
  public :: straight_line
contains
  function straight_line(coordinates) result(is_straight_line)
    real(kind=8), intent(in) :: coordinates(:, :)
    logical :: is_straight_line
    ! Local variables
    integer :: i, j
    real(kind=8) :: slope
    ! Check if the points are collinear
    is_straight_line = .true.
    do i = 2, size(coordinates, 1)
      slope = (coordinates(i, 2) - coordinates(i-1, 2)) / &
              (coordinates(i, 1) - coordinates(i-1, 1))
      do j = i+1, size(coordinates, 1)
        if (abs(slope - (coordinates(j, 2) - coordinates(j-1, 2)) / &
                     (coordinates(j, 1) - coordinates(j-1, 1))) > 1e-8) then
          is_straight_line = .false.
          exit
        end if
      end do
      if (.not. is_straight_line) exit
    end do
  end function straight_line
end module straight_line

program test_straight_line
  use straight_line
  implicit none
  ! Test case 1:
  real(kind=8), parameter :: coordinates1(6, 2) = reshape([1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7], &
                                                         shape([6, 2]))
  logical :: is_straight_line1
  ! Test case 2:
  real(kind=8), parameter :: coordinates2(7, 2) = reshape([1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7], &
                                                         shape([7, 2]))
  logical :: is_straight_line2
  ! Test case 3:
  real(kind=8), parameter :: coordinates3(5, 2) = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], &
                                                         shape([5, 2]))
  logical :: is_straight_line3
  ! Test case 4:
  real(kind=8), parameter :: coordinates4(4, 2) = reshape([1, 2, 3, 4, 5, 6, 7, 8], &
                                                         shape([4, 2]))
  logical :: is_straight_line4
  ! Test case 5:
  real(kind=8), parameter :: coordinates5(3, 2) = reshape([1, 2, 3, 4, 5, 6], &
                                                         shape([3, 2]))
  logical :: is_straight_line5
  ! Test case 6:
  real(kind=8), parameter :: coordinates6(2, 2) = reshape([1, 2, 3, 4], &
                                                         shape([2, 2]))
  logical :: is_straight_line6
  ! Test case 7:
  real(kind=8), parameter :: coordinates7(1, 2) = reshape([1, 2], &
                                                         shape([1, 2]))
  logical :: is_straight_line7
  ! Test case 8:
  real(kind=8), parameter :: coordinates8(0, 2) = reshape([], &
                                                         shape([0, 2]))
  logical :: is_straight_line8
  ! Test case 9:
  real(kind=8), parameter :: coordinates9(10, 2) = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], &
                                                         shape([10, 2]))
  logical :: is_straight_line9
  ! Test case 10:
  real(kind=8), parameter :: coordinates1
🌐 Data from online sources 
def findBestValue(arr, target):
    left = 0
    right = max(arr)
    result = -1
    min_diff = float('inf')

    while left <= right:
        mid = left + (right - left) // 2
        total_sum = sum(min(x, mid) for x in arr)
        if total_sum == target:
            return mid
        elif total_sum > target:
            right = mid - 1
        else:
            left = mid + 1

        if abs(target - total_sum) < min_diff or (
                abs(target - total_sum) == min_diff and mid < result):
            min_diff = abs(target - total_sum)
            result = mid

    return result

The algorithm performs a binary search to find the best value. Initially, the search range is [0, max(arr)]. In each step, it calculates the mid-point of the current search range and computes the sum of the array elements after replacing all elements larger than mid with mid itself. If the sum is equal to the target, it returns the mid-point. Otherwise, the algorithm adjusts the search range based on whether the sum is greater than or less than the target.

At each step, the algorithm also keeps track of the minimum absolute difference between the target and the calculated sum. If a new candidate value (mid-point) is found that would result in a smaller absolute difference or an equal absolute difference and a smaller value, the algorithm updates the result.

Once the search range is exhausted (left > right), the algorithm returns the result.

🌐 Data from online sources 
int findBestValue(vector<int>& arr, int target) {
    int left = 0;
    int right = *max_element(arr.begin(), arr.end());
    int result, min_diff = INT_MAX;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int sum = 0;
        for (int num : arr) {
            sum += min(num, mid);
        }
        if (sum == target) {
            return mid;
        }
        else if (sum > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
        if (abs(target - sum) < min_diff || abs(target - sum) == min_diff && mid < result) {
            min_diff = abs(target - sum);
            result = mid;
        }
    }
    return result;
}

The algorithm performs a binary search to find the best value. Initially, the search range is [0, max(arr)]. In each step, it calculates the mid-point of the current search range and computes the sum of the array elements after replacing all elements larger than mid with mid itself. If the sum is equal to the target, it returns the mid-point. Otherwise, the algorithm adjusts the search range based on whether the sum is greater than or less than the target.

At each step, the algorithm also keeps track of the minimum absolute difference between the target and the calculated sum. If a new candidate value (mid-point) is found that would result in a smaller absolute difference or an equal absolute difference and a smaller value, the algorithm updates the result.

Once the search range is exhausted (left > right), the algorithm returns the result.