Given two integers A, B which are any two terms of an Arithmetic Progression series, and an integer N, the task is to minimize the Nth term of that arithmetic progression.
Note: All the elements of an AP series must be positive.
Examples:
Input: A = 1, B = 6, N = 3
Output: 11
Explanations: First three terms of the given arithmetic progression are: {1, 6, 11}.
Therefore, the required output is 11.Input: A = 20, B = 50, N = 5
Output: 50
Explanations: First Five terms of the given arithmetic progression are: {10, 20, 30, 40, 50}.
Therefore, the required output is 50.
Approach: The problem can be solved by placing A and B at all possible positions in an Arithmetic Progression and check which generates the least possible Nth term. Considering the positions of A and B to be i and j respectively, then the following calculations need to be made:
Common Difference(D) of an AP = (B – A)/(j – i)
First term of an AP = A – (i – 1) * D
Nth term of an AP = First Term + (N – 1)* D
Finally, return the smallest Nth term obtained.
Follow the steps below to solve the problem:
- Initialize a variable, say res to store the smallest possible value of the required Nth term of arithmetic progression.
- Using two nested loops, place A and B at all possible positions in an AP, and calculate the Nth term using above calculations. Keep updating res to store the least value of Nth term obtain.
- Finally, print the value of res as the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest // Nth term of an AP possible int smallestNth( int A, int B, int N) { // Stores the smallest Nth term int res = INT_MAX; for ( int i = 1; i < N; i++) { for ( int j = N; j > i; j--) { // Check if common difference // of AP is an integer if ((B - A) % (j - i) == 0) { // Store the common // difference int D = (B - A) / (j - i); // Store the First Term // of that AP int FirstTerm = A - (i - 1) * D; // Store the Nth term of // that AP int NthTerm = FirstTerm + (N - 1) * D; // Check if all elements of // an AP are positive if (FirstTerm > 0) res = min(res, NthTerm); } } } // Return the least // Nth term obtained return res; } // Driver Code int main() { int N = 3; int A = 1; int B = 6; cout << smallestNth(A, B, N); } |
Java
// Java program to implement // the above approach import java.io.*; class GFG{ // Function to find the smallest // Nth term of an AP possible static int smallestNth( int A, int B, int N) { // Stores the smallest Nth term int res = Integer.MAX_VALUE; for ( int i = 1 ; i < N; i++) { for ( int j = N; j > i; j--) { // Check if common difference // of AP is an integer if ((B - A) % (j - i) == 0 ) { // Store the common // difference int D = (B - A) / (j - i); // Store the First Term // of that AP int FirstTerm = A - (i - 1 ) * D; // Store the Nth term of // that AP int NthTerm = FirstTerm + (N - 1 ) * D; // Check if all elements of // an AP are positive if (FirstTerm > 0 ) res = Math.min(res, NthTerm); } } } // Return the least // Nth term obtained return res; } // Driver Code public static void main (String[] args) { int N = 3 ; int A = 1 ; int B = 6 ; System.out.print(smallestNth(A, B, N)); } } // This code is contributed by code_hunt |
Python3
# Python3 program to implement # the above approach import sys # Function to find the smallest # Nth term of an AP possible def smallestNth(A, B, N): # Stores the smallest Nth term res = sys.maxsize for i in range ( 1 , N): for j in range (N, i, - 1 ): # Check if common difference # of AP is an integer if ((B - A) % (j - i) = = 0 ): # Store the common # difference D = (B - A) / / (j - i) # Store the First Term # of that AP FirstTerm = A - (i - 1 ) * D # Store the Nth term of # that AP NthTerm = FirstTerm + (N - 1 ) * D # Check if all elements of # an AP are positive if (FirstTerm > 0 ): res = min (res, NthTerm) # Return the least # Nth term obtained return res # Driver Code if __name__ = = '__main__' : N = 3 A = 1 B = 6 print (smallestNth(A, B, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the smallest // Nth term of an AP possible static int smallestNth( int A, int B, int N) { // Stores the smallest Nth term int res = Int32.MaxValue; for ( int i = 1; i < N; i++) { for ( int j = N; j > i; j--) { // Check if common difference // of AP is an integer if ((B - A) % (j - i) == 0) { // Store the common // difference int D = (B - A) / (j - i); // Store the First Term // of that AP int FirstTerm = A - (i - 1) * D; // Store the Nth term of // that AP int NthTerm = FirstTerm + (N - 1) * D; // Check if all elements of // an AP are positive if (FirstTerm > 0) res = Math.Min(res, NthTerm); } } } // Return the least // Nth term obtained return res; } // Driver Code public static void Main () { int N = 3; int A = 1; int B = 6; Console.Write(smallestNth(A, B, N)); } } // This code is contributed by code_hunt |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the smallest // Nth term of an AP possible function smallestNth(A, B, N) { // Stores the smallest Nth term let res = Number.MAX_VALUE; for (let i = 1; i < N; i++) { for (let j = N; j > i; j--) { // Check if common difference // of AP is an integer if ((B - A) % (j - i) == 0) { // Store the common // difference let D = (B - A) / (j - i); // Store the First Term // of that AP let FirstTerm = A - (i - 1) * D; // Store the Nth term of // that AP let NthTerm = FirstTerm + (N - 1) * D; // Check if all elements of // an AP are positive if (FirstTerm > 0) res = Math.min(res, NthTerm); } } } // Return the least // Nth term obtained return res; } // Driver code let N = 3; let A = 1; let B = 6; document.write(smallestNth(A, B, N)); // This code is contributed by target_2. </script> |
11
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!