Given three positive integers N, X, and Y(X<Y). The task is to find an array of length N containing both X and Y, and when sorted in increasing order, the array must form an arithmetic progression
Examples:
Input: N = 5, X = 20, Y = 50
Output: 20 30 40 50 10
Explanation: The array when sorted in increasing order forms an arithmetic progression with common difference 10.Input: N = 17, X = 23445, Y = 1000000
Output: 23445 218756 414067 609378 804689 1000000 1195311 1390622 1585933 1781244 1976555 2171866 2367177 2562488 2757799 2953110 3148421
Explanation: The array when sorted in increasing order forms an arithmetic progression with common difference 195311.
Approach: In this problem, it can be observed that if the maximum element is to be minimized, then it can be assumed that Y should be the greatest element. If Y is the greatest, then each of the remaining elements will be less than or equal to Y. If Y is not the greatest element in the array, then elements greater than Y can be considered.
Follow the steps below to solve the given problem:
- Check if some elements which have a common difference are present between X and Y. For this, check if (Y-X) is divisible by (N-1). If it is divisible, then decrease N and the common difference d is given by:
d = (Y-X)/(N-1)
- If it is not divisible, then decrease (n-1) and repeat the above step in a loop till the denominator is non-zero.
- If there don’t exist any such elements between X and Y, then the common difference d is given by:
d = (Y-X)
- Let the resultant array be stored in vector ans. Push the elements found between X and Y in the vector ans to use a for loop.
- If N is not equal to zero, insert the elements in ans starting from (X-d) with common difference d.
- If N is equal to zero, output ans. Otherwise, insert the elements in ans starting from (Y+d) till the required array is obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the array which when// sorted forms an arithmetic progression// and has the minimum possible maximum elementvoid findArray(int N, int X, int Y){ // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array vector<int> ans; // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.push_back(i); } // Stores the element to be inserted in // the resultant vector int i = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && i > 0) { i = i - d; // i must be positive if (i > 0) { ans.push_back(i); // Update N N--; } } // Stores the element to be inserted in // the resultant vector i = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { i = i + d; ans.push_back(i); // Update N N--; } // Output the required array for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << " "; }}// Driver Codeint main(){ // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;class GFG { // Function to find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element static void findArray(int N, int X, int Y) { // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array ArrayList<Integer> ans = new ArrayList<Integer>(); // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.add(i); } // Stores the element to be inserted in // the resultant vector int j = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && j > 0) { j = j - d; // i must be positive if (j > 0) { ans.add(j); // Update N N--; } } // Stores the element to be inserted in // the resultant vector j = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { j = j + d; ans.add(j); // Update N N--; } // Output the required array for (int i = 0; i < ans.size(); ++i) { System.out.print(ans.get(i) + " "); } } // Driver Code public static void main(String[] args) { // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); }} // This code is contributed by gfgking. |
Python3
# python program for the above approach# Function to find the array which when# sorted forms an arithmetic progression# and has the minimum possible maximum elementdef findArray(N, X, Y): # Stores the difference of Y and X r = Y - X # To indicate the absence of required # elements between X and Y d = -1 # Stores the number of required elements # present between X and Y num = 0 # Loop to find the number of required # elements between X and Y for i in range(N - 1, 0, -1): # If r is divisible by i if (r % i == 0): # Stores the common difference # of the elements d = r // i # Decrease num by 1 num = i - 1 # Break from the loop break # If the number of elements present # between X and Y is zero if (d == -1): # Update common difference d = Y - X # Update N N = N - 2 - num # Stores the resultant array ans = [] # Loop to insert the found elements # in the resultant vector for i in range(X, Y + 1, d): ans.append(i) # Stores the element to be inserted in # the resultant vector i = X # Loop to insert elements less than X # in the resultant vector while (N > 0 and i > 0): i = i - d # i must be positive if (i > 0): ans.append(i) # Update N N -= 1 # Stores the element to be inserted in # the resultant vector i = Y # Loop to insert elements greater than Y # in the resultant vector while (N > 0): i = i + d ans.append(i) # Update N N -= 1 # Output the required array for i in range(0, len(ans)): print(ans[i], end=" ")# Driver Codeif __name__ == "__main__": # Given N, X and Y N = 5 X = 20 Y = 50 # Function Call findArray(N, X, Y) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the array which when// sorted forms an arithmetic progression// and has the minimum possible maximum elementstatic void findArray(int N, int X, int Y){ // Stores the difference of Y and X int r = Y - X; // To indicate the absence of required // elements between X and Y int d = -1; // Stores the number of required elements // present between X and Y int num = 0; // Loop to find the number of required // elements between X and Y for (int i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array List<int> ans = new List<int>(); // Loop to insert the found elements // in the resultant vector for (int i = X; i <= Y; i += d) { ans.Add(i); } // Stores the element to be inserted in // the resultant vector int j = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && j > 0) { j = j - d; // i must be positive if (j > 0) { ans.Add(j); // Update N N--; } } // Stores the element to be inserted in // the resultant vector j = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { j = j + d; ans.Add(j); // Update N N--; } // Output the required array for (int i = 0; i < ans.Count; ++i) { Console.Write( ans[i] + " "); }}// Driver Codepublic static void Main(String[] args){ // Given N, X and Y int N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y);}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the array which when // sorted forms an arithmetic progression // and has the minimum possible maximum element function findArray(N, X, Y) { // Stores the difference of Y and X let r = Y - X; // To indicate the absence of required // elements between X and Y let d = -1; // Stores the number of required elements // present between X and Y let num = 0; // Loop to find the number of required // elements between X and Y for (let i = (N - 1); i > 0; i--) { // If r is divisible by i if (r % i == 0) { // Stores the common difference // of the elements d = r / i; // Decrease num by 1 num = i - 1; // Break from the loop break; } } // If the number of elements present // between X and Y is zero if (d == -1) { // Update common difference d = Y - X; } // Update N N = N - 2 - num; // Stores the resultant array let ans = []; // Loop to insert the found elements // in the resultant vector for (let i = X; i <= Y; i += d) { ans.push(i); } // Stores the element to be inserted in // the resultant vector let i = X; // Loop to insert elements less than X // in the resultant vector while (N > 0 && i > 0) { i = i - d; // i must be positive if (i > 0) { ans.push(i); // Update N N--; } } // Stores the element to be inserted in // the resultant vector i = Y; // Loop to insert elements greater than Y // in the resultant vector while (N > 0) { i = i + d; ans.push(i); // Update N N--; } // Output the required array for (let i = 0; i < ans.length; ++i) { document.write(ans[i] + " "); } } // Driver Code // Given N, X and Y let N = 5, X = 20, Y = 50; // Function Call findArray(N, X, Y); // This code is contributed by Potta Lokesh </script> |
Output
20 30 40 50 10
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
