Can Make Arithmetic Progression From Sequence

🏠 ⬅️ ➡️

A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression. Otherwise, return false.

Example 1:

Input: arr = [3,5,1] Output: true Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4] Output: false Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

  • 2 <= arr.length <= 1000
  • -106 <= arr[i] <= 106
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    ! Solve the problem described in the task
    implicit none

    integer, parameter :: n = 3
    integer, dimension(n) :: arr = (/ 3, 5, 1 /)
    logical :: result

    result = canFormArithmeticProgression(arr)
    print '(L1)', result

contains

    function canFormArithmeticProgression(arr) result(result)
        ! Return true if the array can be rearranged to form an arithmetic progression
        implicit none
        integer, intent(in) :: arr(:)
        logical :: result
        integer :: i, j, k, diff

        do i = 1, size(arr)-1
            do j = i+1, size(arr)
                diff = arr(j) - arr(i)
                do k = j+1, size(arr)
                    if (arr(k) - arr(j) == diff) then
                        exit
                    end if
                end do
                if (k > size(arr)) then
                    result = .true.
                    return
                end if
            end do
        end do
        result = .false.
    end function canFormArithmeticProgression
end program main
✅ Compiled
✅ Executed
⚠️ Correct 
module arithmetic_progression

implicit none

contains

function can_form_arithmetic_progression(arr) result(can_form)

integer, intent(in) :: arr(:)
logical :: can_form

! Variables
integer :: n, i, j, diff

! Initialize variables
n = size(arr)
can_form = .false.

! Check if the array has at least two elements
if (n < 2) then
    return
end if

! Check if the array is already in arithmetic progression
diff = arr(2) - arr(1)
do i = 2, n - 1
    if (arr(i + 1) - arr(i) /= diff) then
        return
    end if
end do

! Check if the array can be rearranged to form an arithmetic progression
do i = 1, n - 1
    do j = i + 1, n
        if (arr(j) - arr(i) == diff) then
            can_form = .true.
            exit
        end if
    end do
    if (can_form) then
        exit
    end if
end do

end function can_form_arithmetic_progression

end module arithmetic_progression

program test_arithmetic_progression

use arithmetic_progression
implicit none

! Test case 1:
print *, can_form_arithmetic_progression([3, 5, 1])
! Output:
! .true.

! Test case 2:
print *, can_form_arithmetic_progression([1, 2, 4])
! Output:
! .false.

! Test case 3:
print *, can_form_arithmetic_progression([1, 3, 5, 7, 9])
! Output:
! .true.

! Test case 4:
print *, can_form_arithmetic_progression([1, 2, 3, 4, 5, 6])
! Output:
! .false.

! Test case 5:
print *, can_form_arithmetic_progression([1, 3, 5, 7, 9, 11])
! Output:
! .true.

end program test_arithmetic_progression
🌐 Data from online sources 
def can_construct(s, k):
    char_counts = [0] * 26

    for c in s:
        char_counts[ord(c) - ord('a')] += 1

    odd_count = sum(count % 2 for count in char_counts)

    return odd_count <= k <= len(s)

The algorithm counts the occurrences of each character in the input string s. For each character count, it checks if it is odd - if so, it increases the odd count.

Then, the function checks if the odd count is less than or equal to k (the number of palindrome strings required) and if k is less than or equal to the length of the input string s. If both these conditions are satisfied, the function returns true, meaning it is possible to construct k palindrome strings using all the characters in s. Otherwise, it returns false.

🌐 Data from online sources 
bool canConstruct(std::string s, int k) {
    int char_counts[26] = {0};

    for (char c : s) 
        char_counts[c - 'a']++;

    int odd_count = 0;
    for (int count : char_counts) 
        odd_count += count % 2;

    return odd_count <= k && k <= s.length();
}

The algorithm counts the occurrences of each character in the input string s. For each character count, it checks if it is odd - if so, it increases the odd count.

Then, the function checks if the odd count is less than or equal to k (the number of palindrome strings required) and if k is less than or equal to the length of the input string s. If both these conditions are satisfied, the function returns true, meaning it is possible to construct k palindrome strings using all the characters in s. Otherwise, it returns false.