Given two integers A, B which are any two terms of an Arithmetic Progression series, and an integer N, the task is to construct an Arithmetic Progression series of size N such that it must include both A and B and the Nth term of the AP should be minimum.
Examples:
Input: N = 5, A = 20, B = 50
Output: 10 20 30 40 50
Explanation:
One of the possible AP sequences is {10, 20, 30, 40, 50} having 50 as the 5th value, which is the minimum possible.Input: N = 2, A = 1, B = 49
Output: 1 49
Approach: The Nth Term of an AP is given by XN = X + (N – 1)*d, where X is the first term and d is a common difference. To make the largest element minimum, minimize both x and d. It can be observed that the value of X cannot be more than min(A, B) and the value of d cannot be more than abs(A – B).
- Now, use the same formula to construct the AP for every possible value of x (From 1 to min(A, B)) and d(From 1 to abs(A – B)).
- Now, construct the array arr[] as {x, x + d, x + 2d, …, x + d*(N – 1)}.
- Check if A and B are present in it or not and the Nth element is minimum possible or not. If found to be true, then update the ans[] by the constructed array arr[].
- Otherwise, iterate further and check for other values of x and d.
- Finally, print ans[] as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if both a and// b are present in the AP series or notbool check_both_present(int arr[], int N, int a, int b){ bool f1 = false, f2 = false; // Iterate over the array arr[] for (int i = 0; i < N; i++) { // If a is present if (arr[i] == a) { f1 = true; } // If b is present if (arr[i] == b) { f2 = true; } } // If both are present if (f1 && f2) { return true; } // Otherwise else { return false; }}// Function to print all the elements// of the Arithmetic Progressionvoid print_array(int ans[], int N){ for (int i = 0; i < N; i++) { cout << ans[i] << " "; }}// Function to construct AP series// consisting of A and B with// minimum Nth termvoid build_AP(int N, int a, int b){ // Stores the resultant series int arr[N], ans[N]; // Initialise ans[i] as INT_MAX for (int i = 0; i < N; i++) ans[i] = INT_MAX; int flag = 0; // Maintain a smaller than b if (a > b) { swap(a, b); } // Difference between a and b int diff = b - a; // Check for all possible combination // of start and common difference d for (int start = 1; start <= a; start++) { for (int d = 1; d <= diff; d++) { // Initialise arr[0] as start arr[0] = start; for (int i = 1; i < N; i++) { arr[i] = arr[i - 1] + d; } // Check if both a and b are // present or not and the Nth // term is the minimum or not if (check_both_present(arr, N, a, b) && arr[N - 1] < ans[N - 1]) { // Update the answer for (int i = 0; i < N; i++) { ans[i] = arr[i]; } } } } // Print the resultant array print_array(ans, N);}// Driver Codeint main(){ int N = 5, A = 20, B = 50; // Function Call build_AP(N, A, B); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to check if both a and// b are present in the AP series or notpublic static boolean check_both_present(int[] arr, int N, int a, int b){ boolean f1 = false, f2 = false; // Iterate over the array arr[] for(int i = 0; i < N; i++) { // If a is present if (arr[i] == a) { f1 = true; } // If b is present if (arr[i] == b) { f2 = true; } } // If both are present if (f1 && f2) { return true; } // Otherwise else { return false; }}// Function to print all the elements// of the Arithmetic Progressionpublic static void print_array(int[] ans, int N){ for(int i = 0; i < N; i++) { System.out.print(ans[i] + " "); }}// Function to construct AP series// consisting of A and B with// minimum Nth termpublic static void build_AP(int N, int a, int b){ // Stores the resultant series int[] arr = new int[N]; int[] ans = new int[N]; // Initialise ans[i] as INT_MAX for(int i = 0; i < N; i++) ans[i] = Integer.MAX_VALUE; int flag = 0; // Maintain a smaller than b if (a > b) { // swap(a and b) a += (b - (b = a)); } // Difference between a and b int diff = b - a; // Check for all possible combination // of start and common difference d for(int start = 1; start <= a; start++) { for(int d = 1; d <= diff; d++) { // Initialise arr[0] as start arr[0] = start; for(int i = 1; i < N; i++) { arr[i] = arr[i - 1] + d; } // Check if both a and b are // present or not and the Nth // term is the minimum or not if (check_both_present(arr, N, a, b) && arr[N - 1] < ans[N - 1]) { // Update the answer for(int i = 0; i < N; i++) { ans[i] = arr[i]; } } } } // Print the resultant array print_array(ans, N);}// Driver Codepublic static void main(String[] args){ int N = 5, A = 20, B = 50; // Function call build_AP(N, A, B);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approachimport sys# Function to check if both a and# b are present in the AP series or notdef check_both_present(arr, N, a, b): f1 = False f2 = False # Iterate over the array arr[] for i in range(0, N): # If a is present if arr[i] == a: f1 = True # If b is present if arr[i] == b: f2 = True # If both are present if f1 and f2: return True # Otherwise else: return False# Function to print all the elements# of the Arithmetic Progressiondef print_array(ans, N): for i in range(0, N): print(ans[i], end = " ")# Function to construct AP series# consisting of A and B with# minimum Nth termdef build_AP(N, a, b): INT_MAX = sys.maxsize # Stores the resultant series arr = [None for i in range(N)] # Initialise ans[i] as INT_MAX ans = [INT_MAX for i in range(N)] flag = 0 # Maintain a smaller than b if a > b: # Swap a and b a, b = b, a # Difference between a and b diff = b - a # Check for all possible combination # of start and common difference d for start in range(1, a + 1): for d in range(1, diff + 1): # Initialise arr[0] as start arr[0] = start for i in range(1, N): arr[i] = arr[i - 1] + d # Check if both a and b are # present or not and the Nth # term is the minimum or not if ((check_both_present(arr, N, a, b) and arr[N - 1] < ans[N - 1])): # Update the answer for i in range(0, N): ans[i] = arr[i] # Print the resultant array print_array(ans, N)# Driver Codeif __name__ == "__main__": N = 5 A = 20 B = 50 # Function call build_AP(N, A, B)# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;class GFG{// Function to check if both a and// b are present in the AP series or notstatic bool check_both_present(int[] arr, int N, int a, int b){ bool f1 = false, f2 = false; // Iterate over the array arr[] for(int i = 0; i < N; i++) { // If a is present if (arr[i] == a) { f1 = true; } // If b is present if (arr[i] == b) { f2 = true; } } // If both are present if (f1 && f2) { return true; } // Otherwise else { return false; }}// Function to print all the elements// of the Arithmetic Progressionstatic void print_array(int[] ans, int N){ for(int i = 0; i < N; i++) { Console.Write(ans[i] + " "); }}// Function to construct AP series// consisting of A and B with// minimum Nth termstatic void build_AP(int N, int a, int b){ // Stores the resultant series int[] arr = new int[N]; int[] ans = new int[N]; // Initialise ans[i] as INT_MAX for(int i = 0; i < N; i++) ans[i] = int.MaxValue; // Maintain a smaller than b if (a > b) { // Swap a and b a += (b - (b = a)); } // Difference between a and b int diff = b - a; // Check for all possible combination // of start and common difference d for(int start = 1; start <= a; start++) { for(int d = 1; d <= diff; d++) { // Initialise arr[0] as start arr[0] = start; for(int i = 1; i < N; i++) { arr[i] = arr[i - 1] + d; } // Check if both a and b are // present or not and the Nth // term is the minimum or not if (check_both_present(arr, N, a, b) && arr[N - 1] < ans[N - 1]) { // Update the answer for(int i = 0; i < N; i++) { ans[i] = arr[i]; } } } } // Print the resultant array print_array(ans, N);}// Driver Codestatic public void Main(){ int N = 5, A = 20, B = 50; // Function call build_AP(N, A, B);}}// This code is contributed by akhilsaini |
Javascript
<script>// javascript program for the// above approach// Function to check if both a and// b are present in the AP series or notfunction check_both_present(arr, N, a, b){ let f1 = false, f2 = false; // Iterate over the array arr[] for(let i = 0; i < N; i++) { // If a is present if (arr[i] == a) { f1 = true; } // If b is present if (arr[i] == b) { f2 = true; } } // If both are present if (f1 && f2) { return true; } // Otherwise else { return false; }} // Function to print all the elements// of the Arithmetic Progressionfunction print_array(ans, N){ for(let i = 0; i < N; i++) { document.write(ans[i] + " "); }} // Function to construct AP series// consisting of A and B with// minimum Nth termfunction build_AP(N, a, b){ // Stores the resultant series let arr = Array(N).fill(0); let ans = Array(N).fill(0); // Initialise ans[i] as let_MAX for(let i = 0; i < N; i++) ans[i] = Number.MAX_VALUE; let flag = 0; // Maintain a smaller than b if (a > b) { // swap(a and b) a += (b - (b = a)); } // Difference between a and b let diff = b - a; // Check for all possible combination // of start and common difference d for(let start = 1; start <= a; start++) { for(let d = 1; d <= diff; d++) { // Initialise arr[0] as start arr[0] = start; for(let i = 1; i < N; i++) { arr[i] = arr[i - 1] + d; } // Check if both a and b are // present or not and the Nth // term is the minimum or not if (check_both_present(arr, N, a, b) && arr[N - 1] < ans[N - 1]) { // Update the answer for(let i = 0; i < N; i++) { ans[i] = arr[i]; } } } } // Print the resultant array print_array(ans, N);} // Driver Code let N = 5, A = 20, B = 50; // Function call build_AP(N, A, B); // This code is contributed by avijitmondal1998.</script> |
Output:
10 20 30 40 50
Time Complexity: O(N3)
Auxiliary Space: O(N)
