All Tracks>Problem
Arithmetic Sequence by Exactly One Move
★★★★★

3.4

14 votes
Sorting, Algorithms, Randomized - Quick Sort
Problem

You are given a sequence a=(a1,a2,…,aN) consisting of N integers. You must choose a index i and replace ai by an integer k≠aiexactly once. Determine if you can rearrange a to form an arithmetic sequence or not.

Note that a is an arithmetic sequence if and only if all differences between any two consecutive elements are the same.

Input Format

  • The first line contains a single integer T — the number of test cases.
  • For each testcase:
    • The first line contains one integer n — the length of the sequence.
    • The second line contains n integers a1,a2,...,an.

Output Format

  • For each testcase, output "YES" if the  a can be transformed into an arithmetic sequence. Otherwise, output "NO".

 Constraints

  • 1≤T≤104
  • 2≤n≤105
  • −109≤ai≤109
  • SumofNoveralltestcasesdoesnotexceed106
Sample Input
3
4
0 0 0 0
4
1 2 3 4
4
1 1 3 4
Sample Output
NO
YES
YES
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the second test case:

  • Replace a1 by 5.
  • Then rearrange a into (2,3,4,5).

In the third test case:

  • Replace a2 by 2.
  • Then a is already an arithmetic sequence.

 

Contributers:
Editor Image

?