# Leetcode – Can Make Arithmetic Progression From Sequence Solution

Arithmetic progression is a topic that spans across multiple domains such as mathematics, computer science, and even real-world applications. Leetcode’s “Can Make Arithmetic Progression From Sequence” problem offers a hands-on exercise for understanding and implementing the concept of arithmetic progression in a programmatic way. This problem provides the right mix of array manipulation and sorting algorithms, with a dash of mathematical knowledge. In this comprehensive guide, we will cover multiple approaches to solving the problem, discuss their time and space complexities.

## Problem Statement

Given an array of numbers arr, the task is to return True if the array can be rearranged to form an arithmetic sequence; otherwise, return False.

#### Example

Input: arr = [3, 5, 1]
Output: True
Explanation: The array can be rearranged as [1, 3, 5], which is an arithmetic sequence (1, 3, 5) with a common difference of 2.

## The Brute-Force Approach: Generating All Permutations

One could think of generating all permutations of the array and checking each one to see if it forms an arithmetic sequence. However, this approach would have a time complexity of O(n!), which is not feasible for large arrays. Hence, this approach is generally not recommended for this problem.

## Sorting the Array: The Simplified Approach

The most straightforward way to solve this problem is by sorting the array. Once sorted, it becomes easy to check for an arithmetic progression.

#### Python Code:

def canMakeArithmeticProgression(arr):
arr.sort()
diff = arr - arr

for i in range(1, len(arr) - 1):
if arr[i + 1] - arr[i] != diff:
return False
return True

# Test the function
print(canMakeArithmeticProgression([3, 5, 1]))  # Output should be True

### Time Complexity

The time complexity for sorting the array is O(n log ⁡n) and checking for an arithmetic progression takes O(n), making the overall time complexity O(n log⁡ n).

### Space Complexity

The space complexity is O(1) since no additional space is used other than the input array and some variables.

## Optimized Approach: Using the Formula for Arithmetic Progressions

Arithmetic progressions have a mathematical property: the maximum and minimum elements of the sequence determine all other elements. Specifically, every element can be represented as min+(i×difference), where difference=max−min / length of array−1​. We can use this property to create a more optimized solution:

#### Python Code:

def canMakeArithmeticProgression(arr):
min_val, max_val = min(arr), max(arr)
if min_val == max_val:
return True

n = len(arr)
diff = (max_val - min_val) / (n - 1)

if diff == 0:
return False

visited = set()
for num in arr:
if (num - min_val) % diff != 0:
return False
if num in visited:
return False

return True

# Test the function
print(canMakeArithmeticProgression([3, 5, 1]))  # Output should be True

### Time Complexity

This approach has a time complexity of O(n) for finding the minimum and maximum and another O(n) for the iteration, making it O(n) overall.

### Space Complexity

The space complexity is O(n) for the set visited.

## Edge Cases and Further Considerations

• Small Arrays: What if the array has fewer than 2 elements? In that case, the array can always be considered an arithmetic progression.
• Duplicate Elements: What if the array has duplicate elements? An arithmetic progression must consist of distinct elements.

## Conclusion

The “Can Make Arithmetic Progression From Sequence” problem is a classic example that combines array manipulation with mathematical reasoning. It allows one to explore different approaches ranging from sorting algorithms to the mathematical properties of arithmetic sequences.