Given the three integers N, X, and Y the task is to find an N length arithmetic progression series with the least possible first term containing X and Y.
Examples:
Input: N = 5, X = 10, Y = 15
Output: 5 10 15 20 25
Explanation:
The least possible first term of the AP is 5. Common difference of AP = 5
The given AP contains 10 and 15.Input: N = 10, X = 5, Y = 15
Output: 1 3 5 7 9 11 13 15 17 19
Naive Approach: The simplest approach is to iterate for all the values of possible common differences from 1 to abs(X-Y) and check if there exists an N length AP with the first term greater than 0 and containing both X and Y.
Time Complexity: O(N * abs(X-Y))
Auxiliary Space: O(1)
Efficient Approach: The approach is based on the idea that to include both X and Y in the series, the common difference of the AP must be a factor of abs(X-Y). Below are the steps to solve the problem:
- Iterate from 1 to sqrt(abs(X-Y)) and consider only those common differences which are factors of abs(X-Y).
- For every possible common difference say diff which divides abs(X-Y), find the minimum first term greater than 0 using binary search algorithm.
- Store the minimum first term and the corresponding common difference to print the N length Arithmetic Progression.
Below is the implementation of the above approach:
C++
// C++ program for the approach#include <bits/stdc++.h>using namespace std;// Function that finds the minimum// positive first term including X with given// common difference and the number of termsint minFirstTerm(int X, int diff, int N){ // Stores the first term int first_term; // Initialize the low and high int low = 0, high = N; // Perform binary search while (low <= high) { // Find the mid int mid = (low + high) / 2; // Check if first term is // greater than 0 if (X - mid * diff > 0) { // Store the possible first term first_term = X - mid * diff; // Search between mid + 1 to high low = mid + 1; } else // Search between low to mid-1 high = mid - 1; } // Return the minimum first term return first_term;}// Function that finds the Arithmetic// Progression with minimum possible// first term containing X and Yvoid printAP(int N, int X, int Y){ // Considering X to be // smaller than Y always if (X > Y) swap(X, Y); // Stores the max common difference int maxDiff = Y - X; // Stores the minimum first term // and the corresponding common // difference of the resultant AP int first_term = INT_MAX, diff; // Iterate over all the common difference for (int i = 1; i * i <= maxDiff; i++) { // Check if X and Y is included // for current common difference if (maxDiff % i == 0) { // Store the possible // common difference int diff1 = i; int diff2 = maxDiff / diff1; // Number of terms from // X to Y with diff1 // common difference int terms1 = diff2 + 1; // Number of terms from // X to Y with diff2 // common difference int terms2 = diff1 + 1; // Find the corresponding first // terms with diff1 and diff2 int first_term1 = minFirstTerm(X, diff1, N - terms1); int first_term2 = minFirstTerm(X, diff2, N - terms2); // Store the minimum first term // and the corresponding // common difference if (first_term1 < first_term) { first_term = first_term1; diff = diff1; } if (first_term2 < first_term) { first_term = first_term2; diff = diff2; } } } // Print the resultant AP for (int i = 0; i < N; i++) { cout << first_term << " "; first_term += diff; }}// Driver Codeint main(){ // Given length of AP // and the two terms int N = 5, X = 10, Y = 15; // Function Call printAP(N, X, Y); return 0;} |
Java
// Java program for the approachimport java.util.*;class GFG{// Function that finds the minimum// positive first term including X // with given common difference and // the number of termsstatic int minFirstTerm(int X, int diff, int N){ // Stores the first term int first_term = Integer.MAX_VALUE; // Initialize the low and high int low = 0, high = N; // Perform binary search while (low <= high) { // Find the mid int mid = (low + high) / 2; // Check if first term is // greater than 0 if (X - mid * diff > 0) { // Store the possible first term first_term = X - mid * diff; // Search between mid + 1 to high low = mid + 1; } else // Search between low to mid-1 high = mid - 1; } // Return the minimum first term return first_term;}// Function that finds the Arithmetic// Progression with minimum possible// first term containing X and Ystatic void printAP(int N, int X, int Y){ // Considering X to be // smaller than Y always if (X > Y) { X = X + Y; Y = X - Y; X = X - Y; } // Stores the max common difference int maxDiff = Y - X; // Stores the minimum first term // and the corresponding common // difference of the resultant AP int first_term = Integer.MAX_VALUE, diff = 0; // Iterate over all the common difference for(int i = 1; i * i <= maxDiff; i++) { // Check if X and Y is included // for current common difference if (maxDiff % i == 0) { // Store the possible // common difference int diff1 = i; int diff2 = maxDiff / diff1; // Number of terms from // X to Y with diff1 // common difference int terms1 = diff2 + 1; // Number of terms from // X to Y with diff2 // common difference int terms2 = diff1 + 1; // Find the corresponding first // terms with diff1 and diff2 int first_term1 = minFirstTerm(X, diff1, N - terms1); int first_term2 = minFirstTerm(X, diff2, N - terms2); // Store the minimum first term // and the corresponding // common difference if (first_term1 < first_term) { first_term = first_term1; diff = diff1; } if (first_term2 < first_term) { first_term = first_term2; diff = diff2; } } } // Print the resultant AP for(int i = 0; i < N; i++) { System.out.print(first_term + " "); first_term += diff; }}// Driver Codepublic static void main(String[] args){ // Given length of AP // and the two terms int N = 5, X = 10, Y = 15; // Function call printAP(N, X, Y);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the approachimport sys# Function that finds the minimum# positive first term including X with given# common difference and the number of termsdef minFirstTerm(X, diff, N): # Stores the first term first_term_1 = sys.maxsize # Initialize the low and high low = 0 high = N # Perform binary search while (low <= high): # Find the mid mid = (low + high) // 2 # Check if first term is # greater than 0 if (X - mid * diff > 0): # Store the possible first term first_term_1 = X - mid * diff # Search between mid + 1 to high low = mid + 1 else: # Search between low to mid-1 high = mid - 1 # Return the minimum first term return first_term_1# Function that finds the Arithmetic# Progression with minimum possible# first term containing X and Ydef printAP(N, X, Y): # Considering X to be # smaller than Y always if (X > Y): X = X + Y Y = X - Y X = X - Y # Stores the max common difference maxDiff = Y - X # Stores the minimum first term # and the corresponding common # difference of the resultant AP first_term = sys.maxsize diff = 0 # Iterate over all the common difference for i in range(1, maxDiff + 1): if i * i > maxDiff: break # Check if X and Y is included # for current common difference if (maxDiff % i == 0): # Store the possible # common difference diff1 = i diff2 = maxDiff // diff1 # Number of terms from # X to Y with diff1 # common difference terms1 = diff2 + 1 # Number of terms from # X to Y with diff2 # common difference terms2 = diff1 + 1 # Find the corresponding first # terms with diff1 and diff2 first_term1 = minFirstTerm(X, diff1, N - terms1) first_term2 = minFirstTerm(X, diff2, N - terms2) # Store the minimum first term # and the corresponding # common difference if (first_term1 < first_term): first_term = first_term1 diff = diff1 if (first_term2 < first_term): first_term = first_term2 diff = diff2 # Print the resultant AP for i in range(N): print(first_term, end = " ") first_term += diff # Driver Codeif __name__ == '__main__': # Given length of AP # and the two terms N = 5 X = 10 Y = 15 # Function call printAP(N, X, Y)# This code is contributed by mohit kumar 29 |
C#
// C# program for the approachusing System;class GFG{// Function that finds the minimum// positive first term including X // with given common difference and // the number of termsstatic int minFirstTerm(int X, int diff, int N){ // Stores the first term int first_term = int.MaxValue; // Initialize the low and high int low = 0, high = N; // Perform binary search while (low <= high) { // Find the mid int mid = (low + high) / 2; // Check if first term is // greater than 0 if (X - mid * diff > 0) { // Store the possible first term first_term = X - mid * diff; // Search between mid + 1 to high low = mid + 1; } else // Search between low to mid-1 high = mid - 1; } // Return the minimum first term return first_term;}// Function that finds the Arithmetic// Progression with minimum possible// first term containing X and Ystatic void printAP(int N, int X, int Y){ // Considering X to be // smaller than Y always if (X > Y) { X = X + Y; Y = X - Y; X = X - Y; } // Stores the max common difference int maxDiff = Y - X; // Stores the minimum first term // and the corresponding common // difference of the resultant AP int first_term = int.MaxValue, diff = 0; // Iterate over all the common difference for(int i = 1; i * i <= maxDiff; i++) { // Check if X and Y is included // for current common difference if (maxDiff % i == 0) { // Store the possible // common difference int diff1 = i; int diff2 = maxDiff / diff1; // Number of terms from // X to Y with diff1 // common difference int terms1 = diff2 + 1; // Number of terms from // X to Y with diff2 // common difference int terms2 = diff1 + 1; // Find the corresponding first // terms with diff1 and diff2 int first_term1 = minFirstTerm(X, diff1, N - terms1); int first_term2 = minFirstTerm(X, diff2, N - terms2); // Store the minimum first term // and the corresponding // common difference if (first_term1 < first_term) { first_term = first_term1; diff = diff1; } if (first_term2 < first_term) { first_term = first_term2; diff = diff2; } } } // Print the resultant AP for(int i = 0; i < N; i++) { Console.Write(first_term + " "); first_term += diff; }}// Driver Codepublic static void Main(String[] args){ // Given length of AP // and the two terms int N = 5, X = 10, Y = 15; // Function call printAP(N, X, Y);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function that finds the minimum// positive first term including X// with given common difference and// the number of termsfunction minFirstTerm(X, diff, N){ // Stores the first term let first_term = Number.MAX_VALUE; // Initialize the low and high let low = 0, high = N; // Perform binary search while (low <= high) { // Find the mid let mid = Math.floor((low + high) / 2); // Check if first term is // greater than 0 if (X - mid * diff > 0) { // Store the possible first term first_term = X - mid * diff; // Search between mid + 1 to high low = mid + 1; } else // Search between low to mid-1 high = mid - 1; } // Return the minimum first term return first_term;} // Function that finds the Arithmetic// Progression with minimum possible// first term containing X and Yfunction prletAP(N, X, Y){ // Considering X to be // smaller than Y always if (X > Y) { X = X + Y; Y = X - Y; X = X - Y; } // Stores the max common difference let maxDiff = Y - X; // Stores the minimum first term // and the corresponding common // difference of the resultant AP let first_term = Number.MAX_VALUE, diff = 0; // Iterate over all the common difference for(let i = 1; i * i <= maxDiff; i++) { // Check if X and Y is included // for current common difference if (maxDiff % i == 0) { // Store the possible // common difference let diff1 = i; let diff2 = Math.floor(maxDiff / diff1); // Number of terms from // X to Y with diff1 // common difference let terms1 = diff2 + 1; // Number of terms from // X to Y with diff2 // common difference let terms2 = diff1 + 1; // Find the corresponding first // terms with diff1 and diff2 let first_term1 = minFirstTerm(X, diff1, N - terms1); let first_term2 = minFirstTerm(X, diff2, N - terms2); // Store the minimum first term // and the corresponding // common difference if (first_term1 < first_term) { first_term = first_term1; diff = diff1; } if (first_term2 < first_term) { first_term = first_term2; diff = diff2; } } } // Print the resultant AP for(let i = 0; i < N; i++) { document.write(first_term + " "); first_term += diff; }} // Driver Code // Given length of AP // and the two terms let N = 5, X = 10, Y = 15; // Function call prletAP(N, X, Y);// This code is contributed by souravghosh0416.</script> |
Output:
5 10 15 20 25
Time complexity: O(sqrt(abs(X-Y)) * log(N))
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
