algoadvance

Leetcode 1502. Can Make Arithmetic Progression From Sequence

Problem Statement

Given an array of numbers arr (of length at least 2), determine whether it is possible to reorder the elements of arr to form an arithmetic progression. An arithmetic progression is a sequence of numbers such that the difference between consecutive terms is constant.

Example:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1], both form a valid arithmetic progression.

Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

Clarifying Questions

1. Q: Can the array contain duplicates?
   • A: Yes, the array can contain duplicate elements.
2. Q: Does the order of elements in the final sequence matter?
   • A: No, the order of elements in arr can be rearranged.
3. Q: What is the expected return type?
   • A: The function should return a boolean value (true or false).

Strategy

1. Sort the Array: If we sort the array, any arithmetic progression will have the same difference between consecutive elements.
2. Check the Differences: Calculate the common difference using the first two elements. Iterate through the sorted array and check if the difference between consecutive elements is equal to the common difference.

Steps:

1. Sort the array.
2. Calculate the common difference between the first two elements.
3. Iterate through the rest of the array to ensure that each consecutive pair has the same difference.

Time Complexity

• Sorting the array will take O(n log n).
• Checking the differences will take O(n).
• Therefore, the overall time complexity is O(n log n).

Code

#include <vector>
#include <algorithm>
using namespace std;

bool canMakeArithmeticProgression(vector<int>& arr) {
    // Sort the array
    sort(arr.begin(), arr.end());
    
    // Calculate the common difference
    int commonDiff = arr[1] - arr[0];
    
    // Check the difference between each consecutive elements
    for (int i = 2; i < arr.size(); i++) {
        if (arr[i] - arr[i - 1] != commonDiff) {
            return false;
        }
    }
    
    return true;
}

This function will return true if the array can be rearranged to form an arithmetic progression, and false otherwise.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?