An essential subject for programming interviews is the Array. You'll discover that arrays are used in numerous problems, from complex to easy ones. Since arrays are so standard, you will find them being used in any programming language you select.

This article will look at a problem involving arrays and arithmetic progressions. Array-based questions are the most popular in coding interviews and programming competitions.

In this blog, we will discuss a problem about how many ways to insert a number into the array such that array becomes an arithmetic progression. Before diving directly into the solution, let’s briefly discuss the problem statement.

Problem Statement

Given an array of integers, our task is to count the number of ways to insert an integer into the array such that the array becomes an arithmetic progression upon re-arranging. Display the output as the total number of different integers that can be inserted followed by a new line and then, print all these integers.

Note

A series in which the difference between two subsequent terms is constant is known as an arithmetic progression.

We are allowed to re-arrange the array in any possible way.

The total number of elements in the array is greater than or equal to two.

Input

Total elements in the array (N) = 4

Array = [3, 1, 9, 7]

Output

1 5

Explanation

The numbers in the array are [3, 1, 9, 7].

Suppose we add 5 at any index in the array and re-arrange the array in ascending or descending order. In that case, we get [1, 3, 5, 7, 9], and this forms an Arithmetic Progression because-

Difference between 2nd and 1st term = 3 - 1 = 2

Difference between 3rd and 2nd term = 5 - 3 = 2

Difference between 4th and 3rd term = 7 - 5 = 2

Difference between 5th and 4th term = 9 - 7 = 2

As we can observe, all the consecutive differences have an identical value which is equal to 2. Hence, this sequence is an arithmetic progression with a common difference(d) equal to two. When added to the given array, we can also see that no other number forms an arithmetic progression. So, the output is displayed as 1 which denotes the total number of different elements that can be inserted into the array followed by the number 5 as the single element possible.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Solution Approach

To check whether the current array is in arithmetic progression, simply sort the array and check for all the consecutive differences in the given array. Now, there will be numerous cases possible from here which we will discuss one by one.

Case 1: The total number of elements in the given array is two; there can be three possibilities:

A new integer can be added in front of two elements.

A new integer can be added in the middle of the two elements.

A new integer can be added at the last of the given array.

For the second possibility, it is essential to note that while inserting in between the two elements, the value must be equal to an integer value rather than a decimal value as per the problem statement.

Case 2: If the total number of elements in the given array is greater than two, then two cases can arise:

The array is already progressing arithmetically, i.e., it has a single common difference throughout. Then we can add numbers in the starting and last of the sorted array.

There is no arithmetic progression in the current array. After calculating all potential common differences, the following edge cases are looked for:

We cannot turn the array into an arithmetic progression if there are more than two common differences. As, after inserting an element into the array, there will be at least two common differences in value.

The array cannot be turned into an arithmetic progression if two common differences repeatedly occur in the sequence.

If a common difference ‘a' occurs once, another common difference ‘b’ appears throughout the array. Then, the condition to convert this array into arithmetic progression is a = 2 * b. After inserting an element into the array, the difference of ‘a = (2*b)’ can be converted into a single difference ‘b’. Hence, the array is converted into an arithmetic progression.

Algorithm

Call the ‘solve()’ function to compute all the elements that can be added to the array so that the resultant array is an arithmetic progression.

Check for the size of the given array and make the following two possibilities:

If the size equals 2, make the corresponding case 1 as explained in the approach mentioned above.

If the size is greater than 2, compute all the common differences of the given array, store them in the ‘diff’ array, and make the corresponding case 2 as explained in the abovementioned approach.

Return the ‘ans’ vector, which stores all the possible integers we can insert into the array to convert into Arithmetic Progression.

Display the size of the ‘ans’ vector as the total elements and then the possible elements as the output.

Dry Run

The given array looks like this.

Upon calling the ‘solve’ function for the above array, the following steps will occur, which are as follows:

Step 1 The above array is first sorted by calling the ‘sort()’ function. After sorting, the array looks like this:

Step 2 We will go into the else condition when the total number of elements in the array is greater than two, and we will create the corresponding difference ‘diff’ array for storing the consecutive differences in the array.

Step 3 The above ‘diff’ array is sorted using the ‘sort()’ function. After sorting, the array looks like this:

Step 4 As we can see, the above array already does not form an arithmetic progression because it has greater than one difference in the ‘diff’ array. Now, when two differences are present in the ‘diff’ array and the larger one is present only once, and its value is equal to two times, the smallest difference is checked, and in this case, as it is true, we go further.

Step 5 Now, we will look for the pair whose difference is maximum and insert an element in between that pair.

Step 6 Now, a new element is inserted between the corresponding pair whose difference is equal to the maximum difference whose value is equal to the left element of the pair plus the left element of the pair divided by 2 or the right element of the pair plus the right element of the pair divided by 2.

Finally, the output is displayed as 1 followed by a new line and 5, as only element 5 can be inserted into the array to convert it into an arithmetic progression and 1 here denotes the total elements that can be inserted into the array to convert it into arithmetic progression.

Implementation in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> solve(vector <int> &arr){
int n = arr.size();
// Sort the given array
sort(arr.begin() , arr.end());
// Storing the possible integers that we can insert
vector <int>ans;
// Base case when all elements are same
if(arr[0] == arr[n-1]){
ans.push_back(arr[0]);
return ans;
}
// When total elements in the array = 2
if(n==2){
// Common Difference
int diff = arr[1] - arr[0];
// Adding element to the front
ans.push_back(arr[0] - diff);
// Adding element to the back
ans.push_back(arr[1] + diff);
// Adding element into the middle if possible
if(diff%2==0){
ans.push_back(arr[0] + diff/2);
}
}
// When total elements in the array > 2
else{
// Computing the differences
vector <int> diff;
for(int i=1;i<n;i++){
diff.push_back(arr[i]-arr[i-1]);
}
// Sorting the differences
sort(diff.begin(),diff.end());
// Calculating distinct differences
int ele = diff[0];
int sz = diff.size();
int distinct = 1;
for(int i=0;i<sz;i++){
if(diff[i]!=ele){
++distinct;
}
}
// Already an arithmetic progression
if(distinct==1){
// Adding element to the front
ans.push_back(arr[0] - ele);
// Adding element to the back
ans.push_back(arr[n-1] + ele);
}
else if(distinct==2){
// Storing minimum difference count
int cnt_min=0;
for(int i=0;i<sz;i++){
if(diff[i]==ele){
++cnt_min;
}
}
/*
If the maximum difference occurs only once
and it is equal to 2 times the minimum difference
*/
if(cnt_min==sz-1 && diff[sz-1] == 2*ele){
for(int i=1;i<n;i++){
// Inserting the element
if(arr[i]-arr[i-1] == 2*ele){
ans.push_back(arr[i-1] + ele);
}
}
}
}
}
return ans;
}
int main() {
// Size of the given array
int N = 4;
// Elements of the given array
vector <int> arr(N);
arr[0] = 3;
arr[1] = 1;
arr[2] = 9;
arr[3] = 7;
// Calling the function and storing the result
vector <int> ans = solve(arr);
// Displaying the result
cout<<ans.size()<<"\n";
for(auto i:ans){
cout<<i<<" ";
}
}

Output

Implementation in Java

import java.util.ArrayList;
import java.util.Arrays;
public class MyClass {
static ArrayList<Integer> solve(int arr[]){
int n = arr.length;
// Sort the given array
Arrays.sort(arr);
// Storing the possible integers that we can insert
ArrayList <Integer> ans = new ArrayList<Integer>();
// Base case when all elements are the same
if(arr[0] == arr[n-1]){
ans.add(arr[0]);
return ans;
}
// When total elements in the array = 2
if(n==2){
// Common Difference
int diff = arr[1] - arr[0];
// Adding an element to the front
ans.add(arr[0] - diff);
// Adding element to the back
ans.add(arr[1] + diff);
// Adding element into the middle if possible
if(diff%2==0){
ans.add(arr[0] + diff/2);
}
}
// When total elements in the array > 2
else{
// Computing the differences
int diff[] = new int [n-1];
for(int i=1;i<n;i++){
diff[i-1] = (arr[i]-arr[i-1]);
}
// Sorting the differences
Arrays.sort(diff);
// Calculating distinct differences
int ele = diff[0];
int sz = diff.length;
int distinct = 1;
for(int i=0;i<sz;i++){
if(diff[i]!=ele){
++distinct;
}
}
// Already an arithmetic progression
if(distinct==1){
// Adding element to the front
ans.add(arr[0] - ele);
// Adding element to the back
ans.add(arr[n-1] + ele);
}
else if(distinct==2){
// Storing minimum difference count
int cnt_min=0;
for(int i=0;i<sz;i++){
if(diff[i]==ele){
++cnt_min;
}
}
/*
If the maximum difference occurs only once
and it is equal to 2 times the minimum difference
*/
if(cnt_min==sz-1 && diff[sz-1] == 2*ele){
for(int i=1;i<n;i++){
// Inserting the element
if(arr[i]-arr[i-1] == 2*ele){
ans.add(arr[i-1] + ele);
}
}
}
}
}
return ans;
}
public static void main(String args[]) {
// Size of the given array
int N = 4;
// Elements of the given array
int arr[] = new int [N];
arr[0] = 3;
arr[1] = 1;
arr[2] = 9;
arr[3] = 7;
// Calling the function and storing the result
ArrayList <Integer> ans = solve(arr);
// Displaying the result
System.out.println(ans.size());
for(int i:ans){
System.out.print(i+" ");
}
}
}

Output

Time Complexity

O(N * log(N)), where ‘N’ is the total number of elements in the given array.

Explanation: Using an in-built sorting algorithm, i.e., Merge sort to sort the given array, yields an overall time complexity of O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the total number of elements in the given array.

Explanation: We used an array ‘diff’ to compute the differences between the consecutive elements, yielding an overall space complexity of O(N).

A series in which the difference between two subsequent terms is constant is known as an arithmetic progression.

What do you understand by space complexity?

The space complexity of a program can be defined as the total space taken in the memory by the algorithm concerning its input.

What is an Array?

Each is identified by at least one array index or key, a collection of elements that make up an array data structure. The position of each element in an array can be determined using a mathematical formula from the index tuple.

What is the worst-case complexity of the inbuilt sort function?

The in-built sort function takes up to O(N * log(N)) time to sort a given array in the worst-case.

How is the memory allocation performed for arrays in Java?

Since arrays are objects in Java, their memory is always allocated to the heap.

Conclusion

This article discusses the problem of counting the number of ways to insert an integer into the array such that the array becomes an arithmetic progression upon re-arranging. In detail, we have covered the solution approach to solving the problem, and we saw the implementation of the solution approach in C++ and Java. We also discussed the time complexity and space complexity of the solution approach. We would suggest you solve them to gain more confidence in these kinds of problems. These questions are asked during various coding contests as well as placement tests and thus are very important.

We hope this blog has helped you enhance your knowledge of the array of problems and the Breadth-First Search approach. If you want to improve more, then check out our blogs.

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning, Ninjas!

Live masterclass

Master PowerBI: Solve a Netflix Data Case Study

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO

13 Jul, 2024

06:30 AM

What does it take to become a Data Scientist at Amazon?

by Abhishek Soni, Data Scientist @ Amazon

09 Jul, 2024

01:30 PM

Learn to use AI Tools & ChatGPT to excel as Microsoft SDE

by Pranav Malik, SDE2 @ Microsoft

11 Jul, 2024

01:30 PM

Master PowerBI: Solve a Netflix Data Case Study

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO

13 Jul, 2024

06:30 AM

What does it take to become a Data Scientist at Amazon?