Find the Array which when sorted forms an AP and has Least Maximum

Algorithm -

Step 1. Create a function "findRequiredArray()" to find the array which when sorted forms an AP and has least maximum, which takes 'N,' 'X,' and 'Y' as inputs and return the vector of size 'N' containing both 'X' and 'Y' and when sorted forms an AP.

Step 2. Inside the function "findRequiredArray()," first initialize a variable 'num = N-2' to store the number of elements to be inserted between X and Y. Run a 'while loop' and check if we can get an integer 'common difference' by inserting the 'num' number of elements between X and Y, else decrease 'num' by 1. Break the while loop if the 'num' becomes zero as the minimum number of elements between X and Y can be zero.

Step 3. After finding the number of elements to be inserted between X and Y, calculate the common difference of the AP, which will be formed after sorting the required array. Then create a vector and store the elements between X and Y (both inclusive). Also, create a variable to keep the count of elements inserted in the vector.

Step 4. Check if the number of elements inserted in the vector is less than N, then insert the elements less than X and greater than 0, satisfying the common difference criteria. If still the number of elements in the vector is less than N, insert the elements greater than Y.

Step 5. Finally, return the vector. It will contain the elements which when sorted, will form an AP.

C++ code:

// C++ program to find the array which when sorted forms an AP and has least maximum
#include <bits/stdc++.h>
using namespace std;


// Function to find the array which when sorted forms an AP and has least maximum
vector<int> findRequiredArray(int N, int X, int Y)
{

	// Variable to store the difference of Y and X
	int diff = Y - X;

	// Initialize a variable with "N-2" to store number of elements to be inserted between X and Y
	int num = N-2;

	// Loop to find the maximum possible number of elements between X and Y 
	while(num>=0)
  	{
   		if(diff % (num+1) == 0) {
     		break;
   		}
   		num--;
  	}

	// Variable to store the common difference of the array
	int common_diff = diff/ (num + 1);


	// Declaring a vector to store the required array of elements
	vector<int> ans;

	// Variable to store the count of elements inserted in the reqired array
	int count = 0;

	// First insert all the elements between X and Y including them
	for(int i = X; i <= Y; i+=common_diff)
  	{
   		ans.push_back(i);
   		count++;
  	}
  
    // If the number of elements in the required array is less than N, insert the elements less than X 
   	if(count < N)
      {
		int i = X - common_diff;
		while(i > 0 && count < N)
		{
  			ans.push_back(i);
  			count++;
  			i = i - common_diff;
		}
      }
     
     /*
        If still, the number of elements in the required array is less than N, insert the elements and
        greater than Y, maintaining the common difference
     */    
    if(count < N)
     {
		int i = Y + common_diff;
		while(count < N)
		{
  			ans.push_back(i);
  			count++;
  			i = i + common_diff;
		}
     }

     return ans;
}


// Main Function
int main()
{

	// Given values of N, X and Y
	int N = 5, X = 20, Y = 50;

	/*
	    Call the function to to find the array which when sorted forms an AP and has 
	    least maximum with the given values of N, X and Y
	*/
	vector<int> requiredArray = findRequiredArray(N, X, Y);
	sort(requiredArray.begin(), requiredArray.end());

	cout<<"The required array of positive integers which when sorted forms an AP and has least maximum is: "<<endl;
	for(int i=0; i<requiredArray.size(); i++)
  	{
   		cout<<requiredArray[i]<<" ";
  	}

	return 0;
}

Output:
The required array of positive integers which when sorted forms an AP and has least maximum is: 
20 30 40 50 10 

Algorithm Complexity: 

Time Complexity: O(N )

In the function "findRequiredArray()" to find the array which when sorted forms an AP and has least maximum, loops are run, each having a maximum iteration of N. So, the overall time complexity is O(N), where 'N' is the length of the required array.

Space Complexity: O(N) 

In the function "findRequiredArray()" to find the array which when sorted forms an AP and has least maximum, we have created a vector to store the required array of integers of size N. So, the space complexity is O(N), where 'N' is the length of the required array. 

FAQs

1. What is AP (Arithmetic Progression)? 
   Arithmetic progression (AP) is a sequence of numbers in which the difference of any two consecutive numbers is constant called the common difference.
    
2. In the approach to solve the problem, why we have tried to maximize the number of elements between ‘X’ and ‘Y’?
   In this problem, there is a condition to minimize the maximum possible element of the AP that we are generating and we have to include ‘X’ and ‘Y’ as well. So, if the number of elements between ‘X’ and ‘Y’ will be more, the common difference of the generated AP will be less. And we know that the number of elements of the AP is fixed to be ‘N’ in the problem.
   Hence the largest element of the AP will be the least possible if we will take the least possible common difference of the AP. 

Key takeaways-

This article discussed the problem "Find the array which when sorted forms an AP and has least maximum," the solution approach to this problem,  its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.