[Kattis] Permuted Arithmetic Sequence

“Whatever Nature undertakes, she can only accomplish it in a sequence. She never makes a leap.”

— Goethe

Photo by Steve Johnson on Pexels

An arithmetic sequence is basically a sequence of numbers where each new term is obtained by adding a fixed number to the last one. This fixed number is known the common difference. For example, consider the sequence 1910, 1986, 2062, 2138, 2214. Here, the common difference is 76, since we add 76 to each term to get the next one.

To find the n-th term of an arithmetic sequence, one can use the following formula:

a_n = a₁ + (n-1) * d

here a₁ is the first term of the sequence, d would be the step size of the sequence, and n would be the term that we are looking for. For instance, consider the sequence that was mentioned above [1910, 1986, 2062, 2138, 2214]. This sequences shows the last two appearances of the Halley’s Comet and the next three predictions about its reappearances.

To find the last term of this sequence, or the 5-th term, we can use the formula in this fashion:

a₅ = a₁ + (n-1) * d = 1910 + 4 * 76 = 2214

The formula calculates the 5-th term of the sequence to be 2214, which is correct.

We will be implementing arithmetic sequences in Python, and then use our implementations to solve a programming puzzle from Kattis:

The codes for the Youtube video can be found here:

def is_arithmetic(lst):
    # the first difference
    D = lst[1] - lst[0]
    
    for x in range(2, len(lst)):
        d = lst[x] - lst[x-1]
        
        # check whether they differ
        if d != D:
            return False
        
    return True


# total test cases
n = int(input())

# receive all cases
for _ in range(n):
    # the case
    case = list(map(int, input().split()))[1:]
    
    # arithmetic
    if is_arithmetic(case):
        print('arithmetic')
        
    # permuted arithmetic sequence
    elif is_arithmetic(sorted(case)):
        print('permuted arithmetic')
    
    # not arithmetic
    else:
        print('non-arithmetic')

Related Images: