Valid Boomerang

🏠 ⬅️ ➡️

Given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, return true if these points are a boomerang.

A boomerang is a set of three points that are all distinct and not in a straight line.

Example 1:

Input: points = [[1,1],[2,3],[3,2]] Output: true

Example 2:

Input: points = [[1,1],[2,2],[3,3]] Output: false

Constraints:

  • points.length == 3
  • points[i].length == 2
  • 0 <= xi, yi <= 100
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: dp = selected_real_kind(15)

    integer :: i, j, k
    real(dp), dimension(:, :), allocatable :: points
    logical :: result

    ! read input
    allocate(points(3, 2))
    do i = 1, 3
        read *, points(i, :)
    end do

    ! solve problem
    result = boomerang(points)

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

contains

    function boomerang(points) result(isBoomerang)
        implicit none

        real(dp), intent(in) :: points(:, :)
        logical :: isBoomerang

        integer :: i, j, k
        real(dp) :: det

        isBoomerang = .false.

        do i = 1, size(points, 1) - 2
            do j = i + 1, size(points, 1) - 1
                do k = j + 1, size(points, 1)
                    det = (points(k, 1) - points(j, 1)) * (points(i, 2) - points(j, 2)) &
                        - (points(k, 2) - points(j, 2)) * (points(i, 1) - points(j, 1))
                    if (det /= 0._dp) then
                        isBoomerang = .true.
                        exit
                    end if
                end do
                if (isBoomerang) exit
            end do
            if (isBoomerang) exit
        end do

    end function boomerang

end program main
❌ Compiled
❌ Executed
❌ Correct 
module boomerang
  implicit none
contains
  function is_boomerang(points) result(is_boomerang_)
    real(kind=8), intent(in) :: points(:, :)
    logical :: is_boomerang_
    real(kind=8) :: x1, y1, x2, y2, x3, y3

    x1 = points(1, 1)
    y1 = points(1, 2)
    x2 = points(2, 1)
    y2 = points(2, 2)
    x3 = points(3, 1)
    y3 = points(3, 2)

    is_boomerang_ = (x1 /= x2 .and. x1 /= x3 .and. x2 /= x3 .and. &
                     y1 /= y2 .and. y1 /= y3 .and. y2 /= y3 .and. &
                     x1*y2-x2*y1 /= x1*y3-x3*y1 .and. &
                     x2*y3-x3*y2 /= x1*y3-x3*y1 .and. &
                     x3*y1-x1*y3 /= x1*y2-x2*y1)
  end function is_boomerang
end module boomerang

program main
  use boomerang
  implicit none
  real(kind=8), parameter :: points(3, 2) = reshape([1, 1, 2, 3, 3, 2], shape(points))
  logical :: is_boomerang

  is_boomerang = is_boomerang(points)
  if (is_boomerang) then
    print *, "The points are a boomerang."
  else
    print *, "The points are not a boomerang."
  end if
end program main
🌐 Data from online sources 
def min_k_bit_flips(nums, k):
    n, res, flipped = len(nums), 0, 0
    change = [0] * n
    for i in range(n - k + 1):
        flipped ^= change[i]
        if nums[i] == flipped:
            res += 1
            flipped ^= 1
            if i + k < n:
                change[i + k] ^= 1
    for i in range(n - k + 1, n):
        flipped ^= change[i]
        if nums[i] == flipped:
            return -1
    return res

The algorithm iterates through the array and uses a 'greedy' approach. It flips any subarray starting from the left-most index to ensure no zeroes are left in the array.

To minimize the number of flips, we only flip subarrays if it starts with a 0. We also keep track of previous flips using a separate array (change) to reduce redundant flips.

In the second loop, we check if any 0s are left in the remaining non-flipable part of the array. If so, return -1 as it's not possible to have an all 1s array.

🌐 Data from online sources 
int minKBitFlips(vector<int>& nums, int k) {
    int n = nums.size(), res = 0, flipped = 0;
    vector<int> change(n, 0);
    for (int i = 0; i <= n - k; i++) {
        flipped ^= change[i];
        if (nums[i] ^ flipped == 0) {
            res++;
            flipped ^= 1;
            if (i + k < n) change[i + k] ^= 1;
        }
    }
    for (int i = n - k + 1; i < n; i++) {
        flipped ^= change[i];
        if (nums[i] ^ flipped == 0) return -1;
    }
    return res;
}

The algorithm iterates through the array and uses a 'greedy' approach. It flips any subarray starting from the left-most index to ensure no zeroes are left in the array.

To minimize the number of flips, we only flip subarrays if it starts with a 0. We also keep track of previous flips using a separate array (change) to reduce redundant flips.

In the second loop, we check if any 0s are left in the remaining non-flipable part of the array. If so, return -1 as it's not possible to have an all 1s array.