Create Arithmetic Progressions in the Array

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.

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<<" ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

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+" ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

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

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.

• 0 - 1 BFS
• Number of nodes at a given level in a tree using Breadth-First Search
• Check if there are T number of continuous blocks of 0s or not in the given Binary Matrix

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System 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 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!