702887. Check Arithmetic Progression
Check Arithmetic Progression
Slug: check-arithmetic-progression1842
Difficulty: Basic
Id: 702887
Topic Tags: Arrays, Hash, Data Structures
Company Tags: None
Summary
Given an array of integers, determine if the sequence is in arithmetic progression. An arithmetic progression is a sequence of numbers where each term after the first is obtained by adding a fixed constant to the previous term. For example, the sequence 2, 4, 6, 8 is in arithmetic progression with common difference 2.
Detailed Explanation
To solve this problem, we can use a simple algorithm that iterates through the array and checks if each element is the sum of the previous element and a fixed constant (the common difference). If any pair of elements does not meet this condition, then the sequence is not in arithmetic progression. Here's a step-by-step breakdown:
- Initialize two variables:
common_diffto store the potential common difference andlast_elemto store the last element processed. - Iterate through the array:
- For each element
elem, calculate the potential common difference by subtracting the previous element (last_elem) fromelem. - If this is the first element or if the calculated common difference matches the previously found common difference, update
common_diffand setlast_elemtoelem.
- For each element
- After processing all elements, check if the sequence is in arithmetic progression by verifying that each element minus the previous element equals the common difference.
Time complexity: O(n), where n is the length of the input array. Space complexity: O(1), as we only use a constant amount of space to store the variables.
Optimized Solutions
Java
public boolean checkArithmeticProgression(int[] arr) {
int common_diff = 0;
int last_elem = arr[0];
for (int i = 1; i < arr.length; i++) {
int diff = arr[i] - last_elem;
if (i == 1 || diff == common_diff) {
common_diff = diff;
last_elem = arr[i];
} else {
return false;
}
}
return true;
}