Can Make Arithmetic Progression From Sequence

Can Make Arithmetic Progression From Sequence - Problem

Array Sorting Easy

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: The array [3, 5, 1] can be rearranged to [1, 3, 5] which forms an arithmetic progression with common difference 2.

Input & Output

Example 1 — Basic Case

$ Input: arr = [3,5,1]

› Output: true

💡 Note: We can rearrange the array as [1,3,5] which forms an arithmetic progression with common difference 2.

Example 2 — Already Sorted

$ Input: arr = [1,2,4]

› Output: false

💡 Note: The differences are 2-1=1 and 4-2=2. Since 1 ≠ 2, it cannot form an arithmetic progression.

Example 3 — Equal Elements

$ Input: arr = [1,1,1]

› Output: true

💡 Note: All elements are the same, so the common difference is 0. This forms an arithmetic progression.

Constraints

2 ≤ arr.length ≤ 1000
-10⁶ ≤ arr[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,5,1] - check if can form AP

Process

Sort to [1,3,5] and check differences

Output

Return true since differences are equal

Key Takeaway

🎯 Key Insight: Sort first, then verify all consecutive differences are identical - this is the most efficient approach.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that any arithmetic progression, when sorted, will have equal consecutive differences. The optimal approach is to sort the array first, then verify all consecutive differences are identical. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Property Check	O(n)	O(n)	Use arithmetic progression formula to verify without full sorting
Generate All Permutations	O(n! × n)	O(n)	Try every possible arrangement of numbers to see if any forms arithmetic progression
Sort and Check Differences	O(n log n)	O(1)	Sort the array first, then verify all consecutive differences are equal

Mathematical Property Check — Algorithm Steps

Find minimum and maximum values
Calculate expected common difference: (max-min)/(n-1)
Check if all elements fit this pattern using a hash set

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min/Max

Identify range of values

Calculate Diff

Expected difference = (max-min)/(n-1)

Verify Pattern

Check if all expected values exist

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* arr, int size) {
    if (size <= 2) return true;
    
    int minVal = arr[0], maxVal = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] < minVal) minVal = arr[i];
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    
    // Check if difference is divisible
    if ((maxVal - minVal) % (size - 1) != 0) {
        return false;
    }
    
    int diff = (maxVal - minVal) / (size - 1);
    
    // Check if all expected values exist
    for (int i = 0; i < size; i++) {
        int expected = minVal + i * diff;
        bool found = false;
        for (int j = 0; j < size; j++) {
            if (arr[j] == expected) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(arr, size);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find min/max, then O(n) to verify all elements

✓ Linear Growth

Space Complexity

O(n)

Hash set to store all array elements for verification

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~10 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Property Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler