1.
Introduction-
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity:
6.
FAQs
7.
Key takeaways-
Last Updated: Mar 27, 2024

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

Riya
1 upvote

## Introduction-

This blog will discuss the problem to find the array which when sorted forms an AP and has least maximum. Before going into details of the problem, let's recall what an AP is:

"Arithmetic progression (AP) is a sequence of numbers in which difference of any two consecutive numbers is constant called the common difference."

In this problem, we will be given three positive integers' N', 'X,' and 'Y,' where X is less than Y. We have to find an array of positive integers containing both X and Y, which when sorted forms an AP and the length of the array should be 'N.' One more condition is that the maximum element of the array should be the least possible.

Let's understand the problem with an example:

Suppose N = 5, X = 20 and Y = 50

We have to find an array whose length is 5 containing 20 and 30 and which, when sorted forms an AP and has least maximum.

Consider the array:  arr = {20, 30, 40, 50, 10}

Its sorted form will be: {10, 20, 30, 40, 50}

Here we can see that array "arr" has 5 elements containing both 20 and 50 and, when sorted, forms an AP with a common difference of 10.

Now that we understand the problem, let's discuss the approach to solve it in the next section.

## Solution Approach

This section will discuss the approach to find the array which when sorted forms an AP and has least maximum. In simple words, we have to find the 'N' elements of the required array, out of which two elements, ' X' and 'Y,' are already given.

So, we have to find the remaining 'N-2' elements of the array such that when the array is sorted, it forms an AP, and the maximum element of the array should be the least possible.

The simple logic behind this approach is if we have to make the maximum element of the array the least possible, then we have to insert as many elements as possible between X and Y. The maximum number of elements that we can insert between X and Y is 'N-2'. So, we have to start with 'num = N-2' and keep checking whether it is possible to insert the 'num' number of elements between X and Y. If it is not possible to insert, decrease 'num' by 1.

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 find the required elements of the array. To check whether it is possible to insert the 'num' number of elements between X and Y, check if we can get an integer  'common difference 'by inserting the 'num' number of elements between X and Y.

Also see, Euclid GCD Algorithm

## 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.

## 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.

Live masterclass