# THREEAPFREE - Editorial

Tester: udhav2003
Editorialist: iceknight1093

1170

None

# PROBLEM:

Given a sorted sequence of integers, check whether it is AP-free or not.

# EXPLANATION:

Since N is quite small here (in particular, it’s \leq 100), there’s a rather straightforward solution utilizing nested loops.

From the definition of AP-free sequences, all we need to do is to check whether there are three indices 1 \leq i \lt j \lt k \leq N such that (A_j - A_i) = (A_k - A_j)

To do this, use nested loops to iterate across all possibilities of i, j, and k.
The pseudocode for this would look something like

for i from 1 to N:
for j from i+1 to N:
for k from j+1 to N:
check if a[j] - a[i] == a[k] - a[j]


which you can then translate into code for your language of choice.

# TIME COMPLEXITY

\mathcal{O}(N^3) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 'Yes'
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
if a[j] - a[i] == a[k] - a[j]: ans = 'No'
print(ans)


Is there a better way to solve this rather than N^3 ?

I think if we use hashmap to store all the elements then simply check if(ai+ak==aj/2) if exist simply we return false else we return true

Time complexity: O(n^2)
Space Complexity: O(n)

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;

while (t--) {
int N;
cin >> N;

vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}

int d = arr[1] - arr[0];
bool flag = true;
for (int i = 1; i < N - 1; i++) {
if (arr[i + 1] - arr[i] != d) {
flag = false;
break;
}
}

if (flag) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}

return 0;


}

why is this solution not correct?

I thought the O(n^3) solution will give TLE so I didn’t write the solution and thinking of some another approach

I coded in O(n^2) time complexity and constant space, there is no requirement of hashmap