Find the length of longest arithmetic progression
In the realm of computer science and mathematics, the challenge of discovering patterns within data is a fundamental pursuit. One such problem entails finding the length of the longest arithmetic progression within a sorted array. This problem holds significance in various domains, from data analysis to algorithm optimization. In this article, we will delve into the intricacies of this problem, explore a dynamic programming approach to its solution, and elucidate the steps involved using code examples.
Problem Statement
Given a sorted array of integers, the task is to determine the length of the longest arithmetic progression within the array. An arithmetic progression is a sequence of numbers in which the difference between any two consecutive terms is constant.
Example
Consider the sorted array:
Element: 5 8 10 12 14 16 15
The longest arithmetic progression in this array is "8, 10, 12, 14, 16" with a common difference of 2. Therefore, the length of this arithmetic progression is 5.
Idea to Solve
To tackle this problem efficiently, we employ a dynamic programming approach. The fundamental insight lies in using a two-dimensional array to store information about the length of arithmetic progressions that conclude at specific indices.
Algorithm
- Initialize the result as 2, since the minimum length of an arithmetic progression is 2.
- Create a 2D array named
auxiliary
with all values initialized to 2. This array will store information about the length of arithmetic progressions ending at specific indices. - Loop through the array in reverse order, starting from the second-to-last element.
a. For each index
j
, maintain two pointers:i
(beforej
) andk
(afterj
). b. Whilei
is greater than or equal to 0 andk
is within bounds: i. Ifdata[i] + data[k]
is less than2 * data[j]
, incrementk
. ii. Ifdata[i] + data[k]
is greater than2 * data[j]
, setauxiliary[i][j]
to 2 and decrementi
. iii. Ifdata[i] + data[k]
is equal to2 * data[j]
, setauxiliary[i][j]
toauxiliary[j][k] + 1
, update the result if needed, incrementk
, and decrementi
. c. After the inner loop, set any remainingi
values to 2, as no valid arithmetic progression can be formed with those. d. Move to the previous indexj
. - Print the final result.
Code Solution
// C program
// Find the length of longest arithmetic progression
// In sorted data
#include <stdio.h>
//Display the elements of array
void print_data(int data[], int size)
{
printf("\n Element :");
for (int i = 0; i < size; ++i)
{
printf(" %d", data[i]);
}
}
//returns the maximum of given two numbers
int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
void length_of_longest_ap(int data[], int size)
{
//Display given element
print_data(data, size);
printf("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
printf(" %d\n", size);
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int auxiliary[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
printf(" %d\n", result);
}
int main()
{
//Define the collection of sorted integer values
//This is test inputs
int data1[] = {
-3,
0,
3,
7,
9,
12,
14,
15,
19,
21,
27
};
int data2[] = {
8,
10,
12,
14,
17
};
int data3[] = {
5,
8,
10,
12,
14,
16,
15
};
int data4[] = {
1,
3,
5,
7,
9,
11,
13
};
//Get the size of given data1
int size = sizeof(data1) / sizeof(data1[0]);
length_of_longest_ap(data1, size);
//Get the size of given data2
size = sizeof(data2) / sizeof(data2[0]);
length_of_longest_ap(data2, size);
//Get the size of given data3
size = sizeof(data3) / sizeof(data3[0]);
length_of_longest_ap(data3, size);
//Get the size of given data4
size = sizeof(data4) / sizeof(data4[0]);
length_of_longest_ap(data4, size);
return 0;
}
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
// Java program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
public void print_data(int[] data, int size)
{
System.out.print("\n Element :");
for (int i = 0; i < size; ++i)
{
System.out.print(" " + data[i] );
}
}
//returns the maximum of given two numbers
public int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
public void length_of_longest_ap(int[] data, int size)
{
//Display given element
print_data(data, size);
System.out.print("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
System.out.print(" " + size + "\n");
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int[][] auxiliary = new int[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
System.out.print(" " + result + "\n");
}
public static void main(String[] args)
{
ArithmeticProgression obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int[] data1 = {
-3,
0,
3,
7,
9,
12,
14,
15,
19,
21,
27
};
int[] data2 = {
8,
10,
12,
14,
17
};
int[] data3 = {
5,
8,
10,
12,
14,
16,
15
};
int[] data4 = {
1,
3,
5,
7,
9,
11,
13
};
//Get the size of given data1
int size = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
}
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
//Include header file
#include <iostream>
using namespace std;
// C++ program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
public:
//Display the elements of array
void print_data(int data[], int size)
{
cout << "\n Element :";
for (int i = 0; i < size; ++i)
{
cout << " " << data[i];
}
}
//returns the maximum of given two numbers
int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
void length_of_longest_ap(int data[], int size)
{
//Display given element
this->print_data(data, size);
cout << "\n Result : ";
if (size <= 2)
{
//When have two or less than 2 elements
cout << " " << size << "\n";
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int auxiliary[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = this->max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
cout << " " << result << "\n";
}
};
int main()
{
ArithmeticProgression obj = ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int data1[] = {
-3 , 0 , 3 , 7 , 9 , 12 , 14 , 15 , 19 , 21 , 27
};
int data2[] = {
8 , 10 , 12 , 14 , 17
};
int data3[] = {
5 , 8 , 10 , 12 , 14 , 16 , 15
};
int data4[] = {
1 , 3 , 5 , 7 , 9 , 11 , 13
};
//Get the size of given data1
int size = sizeof(data1) / sizeof(data1[0]);
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = sizeof(data2) / sizeof(data2[0]);
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = sizeof(data3) / sizeof(data3[0]);
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = sizeof(data4) / sizeof(data4[0]);
obj.length_of_longest_ap(data4, size);
return 0;
}
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
//Include namespace system
using System;
// C# program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
public void print_data(int[] data, int size)
{
Console.Write("\n Element :");
for (int i = 0; i < size; ++i)
{
Console.Write(" " + data[i]);
}
}
//returns the maximum of given two numbers
public int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
public void length_of_longest_ap(int[] data, int size)
{
//Display given element
print_data(data, size);
Console.Write("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
Console.Write(" " + size + "\n");
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int[,] auxiliary = new int[size,size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i,size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i,j] = 2;
i--;
}
else
{
auxiliary[i,j] = auxiliary[j,k] + 1;
//Get result
result = max_num(result, auxiliary[i,j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i,j] = 2;
i--;
}
j--;
}
Console.Write(" " + result + "\n");
}
public static void Main(String[] args)
{
ArithmeticProgression obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int[] data1 = {
-3 , 0 , 3 , 7 , 9 , 12 , 14 , 15 , 19 , 21 , 27
};
int[] data2 = {
8 , 10 , 12 , 14 , 17
};
int[] data3 = {
5 , 8 , 10 , 12 , 14 , 16 , 15
};
int[] data4 = {
1 , 3 , 5 , 7 , 9 , 11 , 13
};
//Get the size of given data1
int size = data1.Length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.Length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.Length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.Length;
obj.length_of_longest_ap(data4, size);
}
}
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
<?php
// Php program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
public function print_data( & $data, $size)
{
echo "\n Element :";
for ($i = 0; $i < $size; ++$i)
{
echo " ". $data[$i];
}
}
//returns the maximum of given two numbers
public function max_num($a, $b)
{
if ($a > $b)
{
//When (a) is greater
return $a;
}
//When b is greater than or equal to a
return $b;
}
//returns the length of longest arithmetic progression
public function length_of_longest_ap( & $data, $size)
{
//Display given element
$this->print_data($data, $size);
echo "\n Result : ";
if ($size <= 2)
{
//When have two or less than 2 elements
echo " ". $size ."\n";
return;
}
//Minimum 2 result are possible
$result = 2;
//Create storage to calculate result
$auxiliary = array_fill(0, $size, array_fill(0, $size, 0));
//Loop controlling variables
$i = 0;
$j = 0;
$k = 0;
//Set initial value of created storage
for ($i = 0; $i < $size; $i++)
{
// Set the [i] row and last column value is to 2
$auxiliary[$i][$size - 1] = 2;
}
// Get last-1 position of given data
$j = $size - 2;
while ($j >= 1)
{
$k = $j + 1;
$i = $j - 1;
while ($i >= 0 && $k <= $size - 1)
{
if ($data[$i] + $data[$k] < 2 * $data[$j])
{
$k++;
}
else if ($data[$i] + $data[$k] > 2 * $data[$j])
{
$auxiliary[$i][$j] = 2;
$i--;
}
else
{
$auxiliary[$i][$j] = $auxiliary[$j][$k] + 1;
//Get result
$result = $this->max_num($result, $auxiliary[$i][$j]);
$k++;
$i--;
}
}
while ($i >= 0)
{
$auxiliary[$i][$j] = 2;
$i--;
}
$j--;
}
echo " ". $result ."\n";
}
}
function main()
{
$obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
$data1 = array(-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27);
$data2 = array(8, 10, 12, 14, 17);
$data3 = array(5, 8, 10, 12, 14, 16, 15);
$data4 = array(1, 3, 5, 7, 9, 11, 13);
//Get the size of given data1
$size = count($data1);
$obj->length_of_longest_ap($data1, $size);
//Get the size of given data2
$size = count($data2);
$obj->length_of_longest_ap($data2, $size);
//Get the size of given data3
$size = count($data3);
$obj->length_of_longest_ap($data3, $size);
//Get the size of given data4
$size = count($data4);
$obj->length_of_longest_ap($data4, $size);
}
main();
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
// Node Js program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
print_data(data, size)
{
process.stdout.write("\n Element :");
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + data[i]);
}
}
//returns the maximum of given two numbers
max_num(a, b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
length_of_longest_ap(data, size)
{
//Display given element
this.print_data(data, size);
process.stdout.write("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
process.stdout.write(" " + size + "\n");
return;
}
//Minimum 2 result are possible
var result = 2;
//Create storage to calculate result
var auxiliary = Array(size).fill(0).map(() => new Array(size).fill(0));
//Loop controlling variables
var i = 0;
var j = 0;
var k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = this.max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
process.stdout.write(" " + result + "\n");
}
}
function main()
{
var obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
var data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27];
var data2 = [8, 10, 12, 14, 17];
var data3 = [5, 8, 10, 12, 14, 16, 15];
var data4 = [1, 3, 5, 7, 9, 11, 13];
//Get the size of given data1
var size = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
main();
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
# Python 3 program
# Find the length of longest arithmetic progression
# In sorted data
class ArithmeticProgression :
# Display the elements of array
def print_data(self, data, size) :
print("\n Element :", end = "")
i = 0
while (i < size) :
print(" ", data[i], end = "")
i += 1
# returns the maximum of given two numbers
def max_num(self, a, b) :
if (a > b) :
# When (a) is greater
return a
# When b is greater than or equal to a
return b
# returns the length of longest arithmetic progression
def length_of_longest_ap(self, data, size) :
# Display given element
self.print_data(data, size)
print("\n Result : ", end = "")
if (size <= 2) :
# When have two or less than 2 elements
print(" ", size ,"\n", end = "")
return
# Minimum 2 result are possible
result = 2
# Create storage to calculate result
auxiliary =[[0 for x in range(size)] for y in range(size)]
# Loop controlling variables
i = 0
j = 0
k = 0
# Set initial value of created storage
i = 0
while (i < size) :
# Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2
i += 1
# Get last-1 position of given data
j = size - 2
while (j >= 1) :
k = j + 1
i = j - 1
while (i >= 0 and k <= size - 1) :
if (data[i] + data[k] < 2 * data[j]) :
k += 1
elif(data[i] + data[k] > 2 * data[j]) :
auxiliary[i][j] = 2
i -= 1
else :
auxiliary[i][j] = auxiliary[j][k] + 1
# Get result
result = self.max_num(result, auxiliary[i][j])
k += 1
i -= 1
while (i >= 0) :
auxiliary[i][j] = 2
i -= 1
j -= 1
print(" ", result ,"\n", end = "")
def main() :
obj = ArithmeticProgression()
# Define the collection of sorted integer values
# This is test inputs
data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27]
data2 = [8, 10, 12, 14, 17]
data3 = [5, 8, 10, 12, 14, 16, 15]
data4 = [1, 3, 5, 7, 9, 11, 13]
# Get the size of given data1
size = len(data1)
obj.length_of_longest_ap(data1, size)
# Get the size of given data2
size = len(data2)
obj.length_of_longest_ap(data2, size)
# Get the size of given data3
size = len(data3)
obj.length_of_longest_ap(data3, size)
# Get the size of given data4
size = len(data4)
obj.length_of_longest_ap(data4, size)
if __name__ == "__main__": main()
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
# Ruby program
# Find the length of longest arithmetic progression
# In sorted data
class ArithmeticProgression
# Display the elements of array
def print_data(data, size)
print("\n Element :")
i = 0
while (i < size)
print(" ", data[i])
i += 1
end
end
# returns the maximum of given two numbers
def max_num(a, b)
if (a > b)
# When (a) is greater
return a
end
# When b is greater than or equal to a
return b
end
# returns the length of longest arithmetic progression
def length_of_longest_ap(data, size)
# Display given element
self.print_data(data, size)
print("\n Result : ")
if (size <= 2)
# When have two or less than 2 elements
print(" ", size ,"\n")
return
end
# Minimum 2 result are possible
result = 2
# Create storage to calculate result
auxiliary = Array.new(size) {Array.new(size){0}}
# Loop controlling variables
i = 0
j = 0
k = 0
# Set initial value of created storage
i = 0
while (i < size)
# Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2
i += 1
end
# Get last-1 position of given data
j = size - 2
while (j >= 1)
k = j + 1
i = j - 1
while (i >= 0 && k <= size - 1)
if (data[i] + data[k] < 2 * data[j])
k += 1
elsif(data[i] + data[k] > 2 * data[j])
auxiliary[i][j] = 2
i -= 1
else
auxiliary[i][j] = auxiliary[j][k] + 1
# Get result
result = self.max_num(result, auxiliary[i][j])
k += 1
i -= 1
end
end
while (i >= 0)
auxiliary[i][j] = 2
i -= 1
end
j -= 1
end
print(" ", result ,"\n")
end
end
def main()
obj = ArithmeticProgression.new()
# Define the collection of sorted integer values
# This is test inputs
data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27]
data2 = [8, 10, 12, 14, 17]
data3 = [5, 8, 10, 12, 14, 16, 15]
data4 = [1, 3, 5, 7, 9, 11, 13]
# Get the size of given data1
size = data1.length
obj.length_of_longest_ap(data1, size)
# Get the size of given data2
size = data2.length
obj.length_of_longest_ap(data2, size)
# Get the size of given data3
size = data3.length
obj.length_of_longest_ap(data3, size)
# Get the size of given data4
size = data4.length
obj.length_of_longest_ap(data4, size)
end
main()
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
// Scala program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
def print_data(data: Array[Int], size: Int): Unit = {
print("\n Element :");
var i: Int = 0;
while (i < size)
{
print(" " + data(i));
i += 1;
}
}
//returns the maximum of given two numbers
def max_num(a: Int, b: Int): Int = {
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
def length_of_longest_ap(data: Array[Int], size: Int): Unit = {
//Display given element
print_data(data, size);
print("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
print(" " + size + "\n");
return;
}
//Minimum 2 result are possible
var result: Int = 2;
//Create storage to calculate result
var auxiliary: Array[Array[Int]] = Array.fill[Int](size,size)(0);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
//Set initial value of created storage
i = 0;
while (i < size)
{
// Set the [i] row and last column value is to 2
auxiliary(i)(size - 1) = 2;
i += 1;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data(i) + data(k) < 2 * data(j))
{
k += 1;
}
else if (data(i) + data(k) > 2 * data(j))
{
auxiliary(i)(j) = 2;
i -= 1;
}
else
{
auxiliary(i)(j) = auxiliary(j)(k) + 1;
//Get result
result = max_num(result, auxiliary(i)(j));
k += 1;
i -= 1;
}
}
while (i >= 0)
{
auxiliary(i)(j) = 2;
i -= 1;
}
j -= 1;
}
print(" " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: ArithmeticProgression = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
var data1: Array[Int] = Array(-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27);
var data2: Array[Int] = Array(8, 10, 12, 14, 17);
var data3: Array[Int] = Array(5, 8, 10, 12, 14, 16, 15);
var data4: Array[Int] = Array(1, 3, 5, 7, 9, 11, 13);
//Get the size of given data1
var size: Int = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
}
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
// Swift program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
func print_data(_ data: [Int], _ size: Int)
{
print("\n Element :", terminator: "");
var i: Int = 0;
while (i < size)
{
print(" ", data[i], terminator: "");
i += 1;
}
}
//returns the maximum of given two numbers
func max_num(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
func length_of_longest_ap(_ data: [Int], _ size: Int)
{
//Display given element
self.print_data(data, size);
print("\n Result : ", terminator: "");
if (size <= 2)
{
//When have two or less than 2 elements
print(" ", size ,"\n", terminator: "");
return;
}
//Minimum 2 result are possible
var result: Int = 2;
//Create storage to calculate result
var auxiliary: [[Int]] = Array(repeating : Array( repeating:0 , count:size) , count:size);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
//Set initial value of created storage
i = 0;
while (i < size)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
i += 1;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k += 1;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i -= 1;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = self.max_num(result, auxiliary[i][j]);
k += 1;
i -= 1;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i -= 1;
}
j -= 1;
}
print(" ", result ,"\n", terminator: "");
}
}
func main()
{
let obj: ArithmeticProgression = ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
let data1: [Int] = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27];
let data2: [Int] = [8, 10, 12, 14, 17];
let data3: [Int] = [5, 8, 10, 12, 14, 16, 15];
let data4: [Int] = [1, 3, 5, 7, 9, 11, 13];
//Get the size of given data1
var size: Int = data1.count;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.count;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.count;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.count;
obj.length_of_longest_ap(data4, size);
}
main();
Output
Element : -3 0 3 7 9 12 14 15 19 21 27
Result : 6
Element : 8 10 12 14 17
Result : 4
Element : 5 8 10 12 14 16 15
Result : 5
Element : 1 3 5 7 9 11 13
Result : 7
Time Complexity
The time complexity of this algorithm is approximately O(n^2), where n is the size of the input array. The
nested loops for filling the auxiliary
array contribute to this complexity.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment