An array of N integers is passed as the input. The program must find the combination of integers forming a sequence whose length is more than 4 which satisfies the below conditions.
– The ith index must satisfy arr[i] = arr[i-1] + arr[i-2]
– The length of the sequence must be the maximum possible
– If there are more than one sequences satisfying above two conditions, then print the sequence which contains the smaller value integers.
If there is no such combination of integers, then the program must print -1.
Boundary Condition(s):
1 <= N <= 25
Input Format:
The first line contains N.
The second line contains the N integer values separated by a space.
Output Format:
The first line contains the integer values in the sequence or -1.
Example Input/Output 1:
Input:
9
4 2 7 5 3 8 10 11 19
Output:
2 3 5 8
Explanation:
2 3 5 8 and 3 8 11 19 are the two sequences having same length. But as 2 3 5 8 contains the smaller values, it is printed as the output.
Example Input/Output 2:
Input:
4
1 5 6 10
Output:
-1
Explanation:
Here the sequence 1 5 6 length is not 4. Hence -1 is printed.
# Input the number of elements in the list
num = int(input())
# Input the elements of the list and convert them to integers
lis1 = list(map(int, input().split()))
# Sort the list in ascending order
lis1.sort()
# Initialize two empty lists lis2 and lis3
lis2, lis3 = [], []
# Loop through the elements of lis1 to find the triplet sets
for ele in range(num - 1):
for bar in range(ele + 1, num):
# Add two elements from lis1 to lis2 to form the first two elements of the triplet
lis2.append(lis1[ele])
lis2.append(lis1[bar])
t1, t2 = 0, 1
# Loop through the remaining elements of lis1 to check if they can complete the triplet
for foo in range(bar + 1, num):
if lis1[foo] == (lis2[t1] + lis2[t2]):
lis2.append(lis1[foo])
t1 += 1
t2 += 1
# Append the found triplet (lis2) to lis3
lis3.append(lis2)
# Reset lis2 for the next iteration
lis2 = []
# Initialize two empty lists lis4 and lis5
lis4, lis5 = [], []
# Find the length of each triplet in lis3 and store it in lis4
for ele in lis3:
lis4.append(len(ele))
# Find the maximum length of triplets in lis3
maxima = max(lis4)
# If the maximum length is less than 4, it means no valid triplet exists, so print -1 and exit
if maxima < 4:
print(-1)
exit()
# Find the sum of each triplet in lis3 and store it in lis5
for ele in lis3:
if len(ele) == maxima:
lis5.append(sum(ele))
# Find the minimum sum of triplets in lis5
min_sum = min(lis5)
# Find the triplet with the minimum sum in lis3 and print its elements
for ele in lis3:
if sum(ele) == min_sum:
print(*ele)
break
#include <stdio.h>
int main() {
int num;
scanf("%d", &num); // Input the number of elements in the list
int lis1[num];
for (int i = 0; i < num; i++) {
scanf("%d", &lis1[i]); // Input the elements of the list
}
// Sort the list in ascending order using bubble sort
for (int i = 0; i < num - 1; i++) {
for (int j = 0; j < num - i - 1; j++) {
if (lis1[j] > lis1[j + 1]) {
int temp = lis1[j];
lis1[j] = lis1[j + 1];
lis1[j + 1] = temp;
}
}
}
int lis2[3] = {0}; // Initialize an array to store the triplet
int lis3[20][3]; // Initialize a 2D array to store all the found triplets
int count = 0; // Initialize a variable to keep track of the number of found triplets
// Loop through the elements of lis1 to find the triplet sets
for (int ele = 0; ele < num - 1; ele++) {
for (int bar = ele + 1; bar < num; bar++) {
lis2[0] = lis1[ele]; // Add the first element to lis2
lis2[1] = lis1[bar]; // Add the second element to lis2
int t1 = 0, t2 = 1;
// Loop through the remaining elements of lis1 to check if they can complete the triplet
for (int foo = bar + 1; foo < num; foo++) {
if (lis1[foo] == (lis2[t1] + lis2[t2])) {
lis2[t1 + 2] = lis1[foo]; // Add the third element to lis2
t1++;
t2++;
}
}
// Copy the found triplet (lis2) to lis3
for (int i = 0; i < 3; i++) {
lis3[count][i] = lis2[i];
}
count++;
// Reset lis2 for the next iteration
lis2[0] = lis2[1] = lis2[2] = 0;
}
}
int lis4[count]; // Initialize an array to store the lengths of each triplet
for (int i = 0; i < count; i++) {
lis4[i] = 3; // Since all triplets have 3 elements, set the length to 3
}
int maxima = lis4[0]; // Initialize maxima as the length of the first triplet
// Find the maximum length of triplets in lis3
for (int i = 1; i < count; i++) {
if (lis4[i] > maxima) {
maxima = lis4[i];
}
}
// If the maximum length is less than 4, it means no valid triplet exists, so print -1 and exit
if (maxima < 4) {
printf("-1n");
return 0;
}
int lis5[20]; // Initialize an array to store the sums of each triplet
for (int i = 0; i < count; i++) {
// Calculate the sum of each triplet and store it in lis5
lis5[i] = lis3[i][0] + lis3[i][1] + lis3[i][2];
}
int min_sum = lis5[0]; // Initialize min_sum as the sum of the first triplet
// Find the minimum sum of triplets in lis5
for (int i = 1; i < count; i++) {
if (lis5[i] < min_sum) {
min_sum = lis5[i];
}
}
// Find the triplet with the minimum sum in lis3 and print its elements
for (int i = 0; i < count; i++) {
if (lis5[i] == min_sum) {
printf("%d %d %dn", lis3[i][0], lis3[i][1], lis3[i][2]);
break;
}
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt(); // Input the number of elements in the list
int[] lis1 = new int[num];
for (int i = 0; i < num; i++) {
lis1[i] = sc.nextInt(); // Input the elements of the list
}
// Sort the list in ascending order using selection sort
for (int i = 0; i < num - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < num; j++) {
if (lis1[j] < lis1[minIndex]) {
minIndex = j;
}
}
int temp = lis1[i];
lis1[i] = lis1[minIndex];
lis1[minIndex] = temp;
}
int[] lis2 = new int[3]; // Initialize an array to store the triplet
int[][] lis3 = new int[20][3]; // Initialize a 2D array to store all the found triplets
int count = 0; // Initialize a variable to keep track of the number of found triplets
// Loop through the elements of lis1 to find the triplet sets
for (int ele = 0; ele < num - 1; ele++) {
for (int bar = ele + 1; bar < num; bar++) {
lis2[0] = lis1[ele]; // Add the first element to lis2
lis2[1] = lis1[bar]; // Add the second element to lis2
int t1 = 0, t2 = 1;
// Loop through the remaining elements of lis1 to check if they can complete the triplet
for (int foo = bar + 1; foo < num; foo++) {
if (lis1[foo] == (lis2[t1] + lis2[t2])) {
lis2[t1 + 2] = lis1[foo]; // Add the third element to lis2
t1++;
t2++;
}
}
// Copy the found triplet (lis2) to lis3
System.arraycopy(lis2, 0, lis3[count], 0, 3);
count++;
// Reset lis2 for the next iteration
lis2[0] = lis2[1] = lis2[2] = 0;
}
}
int[] lis4 = new int[count]; // Initialize an array to store the lengths of each triplet
for (int i = 0; i < count; i++) {
lis4[i] = 3; // Since all triplets have 3 elements, set the length to 3
}
int maxima = lis4[0]; // Initialize maxima as the length of the first triplet
// Find the maximum length of triplets in lis3
for (int i = 1; i < count; i++) {
if (lis4[i] > maxima) {
maxima = lis4[i];
}
}
// If the maximum length is less than 4, it means no valid triplet exists, so print -1 and exit
if (maxima < 4) {
System.out.println("-1");
return;
}
int[] lis5 = new int[count]; // Initialize an array to store the sums of each triplet
for (int i = 0; i < count; i++) {
// Calculate the sum of each triplet and store it in lis5
lis5[i] = lis3[i][0] + lis3[i][1] + lis3[i][2];
}
int min_sum = lis5[0]; // Initialize min_sum as the sum of the first triplet
// Find the minimum sum of triplets in lis5
for (int i = 1; i < count; i++) {
if (lis5[i] < min_sum) {
min_sum = lis5[i];
}
}
// Find the triplet with the minimum sum in lis3 and print its elements
for (int i = 0; i < count; i++) {
if (lis5[i] == min_sum) {
System.out.println(lis3[i][0] + " " + lis3[i][1] + " " + lis3[i][2]);
break;
}
}
}
}
