Question

Arithmetic progression

def arithmetic_progression(elems):

An arithmetic progression is a numerical sequence so that the stride between each two consecutive elements is constant throughout the sequence. For example, [4, 8, 12, 16, 20] is an arithmetic progression of length 5, starting from the value 4 with a stride of 4.

Given a list of elems guaranteed to consist of positive integers listed in strictly ascending order, find and return the longest arithmetic progression whose all values exist somewhere in that sequence. Return the answer as a tuple (start, stride, n) of the values that define the progression. To ensure that the answer is unique for automated testing, if there exist several progressions of the same length, return the one with the smallest start. If there exist several progressions of equal length from the same start, return the progression with the smallest stride.

elems	Expected result
[42]	(42, 0, 1)
[2, 4, 6, 7, 8, 12, 17]	(2, 2, 4)
[1, 2, 36, 49, 50, 70, 75, 98, 104, 138, 146, 148, 172, 206, 221, 240, 274, 294, 367, 440]	(2, 34, 9)
[2, 3, 7, 20, 25, 26, 28, 30, 32, 34, 36, 41, 53, 57, 73, 89, 94, 103, 105, 121, 137, 181, 186, 268, 278, 355, 370, 442, 462, 529, 554, 616, 646, 703]	(7, 87, 9)
list(range(1000000))	(0, 1, 1000000)

Answer 1

Approach used:

The longest length of an arithmetic progression can be solved using dynamic programming. Before moving into solving it use dynamic programming. We need to remember following end cases and points:

• if length of input is 1, then answer is simply (a1, 0, 1)
• if length of input is 2, then answer is simply (a1, a2-a1, 2)
• Any 2 numbers in the input can form an AP of length 2. So if length >= 2, max AP length is going to be greater then or equal to 2.
• We are going to solve it using bottom-up approach moving right to left

In order to solve it, we are going to make a table dp[n][n], where n = input length. We initialize all the values in table with 0. The value stored at dp[i][j] will indicate the length of the longest AP with numbers at position i and j as first two elements of AP. Hence, dp[i][n-1] is always going to be 2.

To fill the remaining table, we do the folloing:

• Iterate j from n-2 to 1
• For each index j, find index i (i<j) and index k (k>j) such that ai, aj, ak are in AP.
• when we find them, we update our table as dp[i][j] = dp[j][k]+1

Now some may ask why dp[i][j] = dp[j][k]+1? Why not update dp[j][k] or dp[i][k]? It is because the value stored at dp[i][j] will indicate the length of the longest AP with numbers at position i and j as first two elements of AP.

----------------------------------------------------

Below is the python code:

Screenshot:
def longestAP(set): I. This function accepts a list and returns a tuple (start, stride, n) n = len(set) if n==1: #end case when n=1 return (set[@], 0, 1) if n==2: #end case when n==2 return (set[@], set[1]-set[@],2) #when n>2 : dp = [[0 for x in range(n)] for y in range(n)] #create nxn table for i in range(n-1): dp[i][n - 1] = 2 #numbers at i and n-1 widt always form an AP of Length 2.

for j in range(n 2, 0, -1): *j iterates over values n-2 to 1 #we try to find i, j and k such that set[i], set[i] and set[k] ore in AP i- j - 1 k = j + 1 while(i >= 0 and k <= n 1): if (set[i] + set[k] < 2 set[j]): k += 1 elif (set[i] + set[k] > 2 * set[j]): dp[i][j] = 2 #set do[i][j] = 2 because table fitting is done using i and j in bottom up manner i - 1 else: #i, j and k are found dp[i][j] dp[j][k] + 1 #update result in do table #j can be part of many APs so decrease i and increase k i 1 k += 1 #if loop ends because of k>n-1 fitt tabte do[i][j] for remaining i while (i >= 0): dp[i][j] = 2 #i and j wilt form AP of Length 2 i - 1 -= lap maxi = @ maxi for i in range(n): for j in range(n): if dp[i][j] > lap: #find max 4P Length lap = dp[i][j] maxi maxj = il i return (set[maxi], set[maxj]-set[maxi],lap)

Code as text:

def longestAP(set):
'''
This function accepts a list and
returns a tuple (start, stride, n)
'''
n = len(set)
  
if n==1: #end case when n=1
return (set[0], 0, 1)
  
if n==2: #end case when n==2
return (set[0],set[1]-set[0],2)
  
#when n>2 :
dp = [[0 for x in range(n)] for y in range(n)] #create nxn table
  
for i in range(n-1):
dp[i][n - 1] = 2 #numbers at i and n-1 will always form an AP of length 2.
  

for j in range(n - 2, 0, -1): #j iterates over values n-2 to 1
#we try to find i, j and k such that set[i], set[j] and set[k] are in AP
i = j - 1
k = j + 1
while(i >= 0 and k <= n - 1):
if (set[i] + set[k] < 2 * set[j]):
k += 1
elif (set[i] + set[k] > 2 * set[j]):
dp[i][j] = 2 #set dp[i][j] = 2 because table filling is done using i and j in bottom up manner
i -= 1
else:
#i, j and k are found
dp[i][j] = dp[j][k] + 1 #update result in dp table
#j can be part of many APs so decrease i and increase k
i -= 1
k += 1
#if loop ends because of k>n-1 fill table dp[i][j] for remaining i
while (i >= 0):
dp[i][j] = 2 #i and j will form AP of length 2
i -= 1
  
lap = 0
maxi = 0
maxj = 0
  
for i in range(n):
for j in range(n):
if dp[i][j] > lap: #find max AP length
lap = dp[i][j]
maxi = i
maxj = j
  
return (set[maxi],set[maxj]-set[maxi],lap)

-------------------------------------------------

Output:

print(longestAP([42])) (42, 0, 1) print(longestAP([2, 4, 6, 7, 8, 12, 17])) (2, 2, 4) print(longestAP([1, 2, 36, 49, 50, 70, 75, 98, 104, 138, 146, 148, 172, 206, 221, 240, 274, 294, 367, 440])) (2, 34, 9) print(longestAP([2, 3, 7, 20, 25, 26, 28, 30, 32, 34, 36, 41, 53, 57, 73, 89, 94, 103, 105, 121, 137, 181, 186, 268, 278, 355, 370, 442, 462, 529, 554, 616, 646, 703])) (7, 87, 9)

=========== END ============

The last test list(range(1000000)) was unable to run on my computer

PLEASE DON'T FORGET TO LIKE.. ..IT IS OF MUCH IMPORTANCE TO ME*****†****""""""