We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can Make Arithmetic Progression From Sequence

Number: 1626

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an array of numbers, determine if it can be rearranged to form an arithmetic progression, where the difference between any two consecutive elements is the same.

Key Insights

  • Sorting the array aligns the elements in order so that any arithmetic progression becomes apparent.
  • After sorting, compute the difference between the first two elements as the target common difference.
  • Verify that every consecutive pair of elements has the same difference.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements. Space Complexity: O(n) depending on the sorting algorithm implementation.

Solution

The solution involves first sorting the array to order the elements. Once sorted, the common difference is calculated using the difference between the first two elements. Then, iterate over the sorted array to ensure that each consecutive pair of numbers has the same difference. If any difference mismatches, the function returns false. If all consecutive differences match, the array can be rearranged into an arithmetic progression and the function returns true.

Code Solutions

# Function to check if an arithmetic progression can be formed from the given array

def can_make_arithmetic_progression(arr):
    # Sort the array in non-decreasing order
    arr.sort()
    # Calculate the common difference using the first two elements
    common_diff = arr[1] - arr[0]
    # Traverse the sorted array and ensure each adjacent pair has the same difference
    for i in range(1, len(arr)):
        # If the difference deviates, return False
        if arr[i] - arr[i - 1] != common_diff:
            return False
    # If all differences are consistent, return True
    return True

# Example usage:
# arr = [3, 5, 1]
# print(can_make_arithmetic_progression(arr))  # Expected output: True
← Back to All Questions