Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Solution Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Frequently Asked Questions
4.1.
What do you mean by an Arithmetic Progression?
4.2.
What do you understand by space complexity?
4.3.
What is an Array?
4.4.
What is the worst-case complexity of the inbuilt sort function?
4.5.
How is the memory allocation performed for arrays in Java?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Create Arithmetic Progressions in the Array

Author Sahil Setia
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

title image

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 

  1. A series in which the difference between two subsequent terms is constant is known as an arithmetic progression.
  2. We are allowed to re-arrange the array in any possible way.
  3. 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.

Also read, Euclid GCD Algorithm

Get the tech career you deserve, faster!
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:

  1. A new integer can be added in front of two elements.
     
  2. A new integer can be added in the middle of the two elements.
     
  3. 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:

  1. 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.
     
  2. There is no arithmetic progression in the current array. After calculating all potential common differences, the following edge cases are looked for:

    1. 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.
       
    2. The array cannot be turned into an arithmetic progression if two common differences repeatedly occur in the sequence.
       
    3. 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

  1. 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.
     
  2. Check for the size of the given array and make the following two possibilities:
    1. If the size equals 2, make the corresponding case 1 as explained in the approach mentioned above.
       
    2. 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.
       
  3. Return the ‘ans’ vector, which stores all the possible integers we can insert into the array to convert into Arithmetic Progression.
     
  4. 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.

Dry run image 1

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:
Dry run image 2
  • 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.
Dry run image 3
  • Step 3
    The above ‘diff’ array is sorted using the ‘sort()’ function. After sorting, the array looks like this:
Dry run image 4
  • 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.
Dry run image 5
  • Step 5
    Now, we will look for the pair whose difference is maximum and insert an element in between that pair.
Dry run image 6
  • 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.
Dry run image 7

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

Output image

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

Output image

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

Must Read Array of Objects in Java

Frequently Asked Questions

What do you mean by an Arithmetic Progression?

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.

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

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 problemsinterview 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