Cheerio Contest 1 J5 - Arithmetic Sequence

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

You are given a list of N integers a_1, a_2, \dots, a_N. Determine whether or not you can modify the list into an arithmetic sequence by rearranging the list and/or changing the value of at most 1 number.

An arithmetic sequence is a sequence in which each term is obtained by adding the previous term by a constant number, called the common difference. For example, 2, 5, 8, 11 is an arithmetic sequence with a common difference of 3.

Constraints

For all subtasks:

  • 1 \le a_i \le 10^9
Points Awarded N
6 points 2 \le N \le 400
5 points 2 \le N \le 4\,000
4 points 2 \le N \le 2 \times 10^5

Input Specification

The first line contains one integer N.

The second line contains N integers a_i.

Output Specification

Output YES if the list can be modified to become an arithmetic sequence and NO otherwise.

Sample Input 1

4
3 1 5 10

Sample Output 1

YES

Explanation for Sample Output 1

We can change the 4^{\text{th}} number in the list to be 7. The list of numbers becomes 3, 1, 5, 7, which can be rearranged to form the arithmetic sequence 1, 3, 5, 7.

Sample Input 2

5
3 6 9 12 15

Sample Output 2

YES

Explanation for Sample Output 2

The list is already an arithmetic sequence, so no changes are necessary.


Comments


  • 0
    ColonelBy_team10  commented on June 30, 2022, 7:57 p.m.

    Can change element in array to negative number?