Last Updated on March 23, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
Medium
Problem Statement (Simplified):
Print the total number of cases in which the current array sequence becomes Arithmetic Progression by adding a number at any place, also print the numbers.
- Arithmetic Progression: Sequence increasing or decreasing with a constant
K(common difference) is known as Arithmetic Progression.
See original problem statement here
Input:
1
3
4 2 6
Output:
2
0 8
Explanation:
In the given array,
If we introduce 0, the array becomes [0, 2, 4, 6] which is an Arithmetic Progression with common difference 2.
If we introduce 8, the array becomes [2, 4, 6, 8] which is an Arithmetic Progression with common difference 2.
So, we print 2, because there are two such numbers, also we print 0 and 8 because they're required numbers.Solving Approach :
Bruteforce Approach:
1) We sort the array and introduce numbers one by one. After adding one number, we check if the current formed sequence is Arithmetic Progression or not. If yes, increase the count and print the note the added number.
2) After the whole array is traversed for adding the number, we print the count and print all the numbers noted in a row.
3) This approach takes O(n*log(n)) for sorting array using merge sort, also O(n+1) to add numbers. This takes O(n) for checking if the current sequence is Arithmetic Progression or not for every addition. Hence total time complexity of this approach is O(n*log(n) + n2). This approach takes longer times to process a large number of queries, so we move to a new efficient approach.
Efficient Approach:
- As we know Arithmetic Progression is always increasing or decreasing, so we sort the array so that it can be arranged in an increasing sequence.
- If the array contains only a
single element, it is already an Arithmetic Progression, so no further elements are required to make it Arithmetic Progression. - If the array contains only
2 elements, there can be three possibilities :- A number can be added in front, where the common difference between the number and the first element is the same as the difference between array elements.
- A number can be added in last, where the common difference between the number and last element is the same as the difference between array elements.
- A number can be added in middle, that would be the average of two elements in the array, where the sum of both elements must be even.
- If the array contains more than 2 elements, the following cases, can arise :
- CASE-1: If the current array is already an Arithmetic Progression, we can add numbers in the last and first position as we discussed in point 2. Here no middle element is added.
- CASE-2: If the array is not an Arithmetic Progression, we calculate all possible common differences, and see for these cases :
- If there are more than 2 common differences, there is no way to convert the current array into Arithmetic Progression by adding a number.
- If there are two common difference, where both appears multiple times in sequence (multiple elements have them as common difference), then there is no possible way to convert the current array into an Arithmetic Progression.
- If there appears a common difference which is present only once, and other common difference appears the rest of the times. Let’s say multiple elements have
aas common difference and there exist two elements whose difference isb. We can convert current sequence into an arithmetic progression only and only ifbis double ofa(2b = a), hence a number can be added between elements having common differenceb, and number would beA[k]+aorA[k+1]-awhere A[k+1]-A[k] = b.
Solutions
#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int d[n], count=0;
int a[n+1];
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
if(n==1){
printf("-1\n");
continue;
}
mergeSort(a,1,n);
if(a[1]==a[n])
{
printf("1\n");
printf("%d\n",a[1]);
continue;
}
for(int i=2;i<=n;i++)
d[count++] = a[i]-a[i-1];
mergeSort(d,0,count-1);
int len=d[0];
if(n==2 && len%2==0){
printf("3\n");
printf("%d %d %d\n",a[1]-len,a[1]+len/2,a[2]+len);
continue;
}
if(count>2 && d[0]!=d[count-2])
printf("0\n");
else if(count>1 && d[count-1]>len){
if(d[count - 1] != len + len)
printf("0\n");
else
{
printf("1\n");
for(int i=2;i<=n;i++)
if(a[i]-a[i-1]!=len)
printf("%d\n",a[i-1]+len);
}
}
else{
printf("2\n");
printf("%d %d\n",a[1]-len,a[n]+len);
}
}
}
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1]={0};
int right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int d[n], count=0;
int a[n+1];
for(int i=1;i<=n;i++)
cin>>a[i];
if(n==1){
cout<<-1<<endl;
continue;
}
mergeSort(a,1,n);
if(a[1]==a[n])
{
cout<<1<<endl<<a[1]<<endl;
continue;
}
for(int i=2;i<=n;i++)
d[count++] = a[i]-a[i-1];
mergeSort(d,0,count-1);
int len=d[0];
if(n==2 && len%2==0){
cout<<3<<endl<<a[1]-len<< " "<<a[1]+len/2<<" "<<a[2]+len<<endl;
continue;
}
if(count>2 && d[0]!=d[count-2])
cout<<"0"<<endl;
else if(count>1 && d[count-1]>len){
if(d[count - 1] != len + len)
cout<<"0"<<endl;
else
{
cout<<1<<endl;
for(int i=2;i<=n;i++)
if(a[i]-a[i-1]!=len)
cout<<a[i-1]+len<<endl;
}
}
else
cout<<2<<endl<<a[1]-len<<" "<<a[n]+len<<endl;
}
}
import java.util.*;
import java.io.*;
public class Main
{
static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int d[] = new int[n], count=0;
int a[] = new int[n+1];
for(int i=1;i<=n;i++)
a[i] = sc.nextInt();
if(n==1){
System.out.println("-1");
continue;
}
mergeSort(a,1,n);
if(a[1]==a[n])
{
System.out.println("1");
System.out.println(a[1]);
continue;
}
for(int i=2;i<=n;i++)
d[count++] = a[i]-a[i-1];
mergeSort(d,0,count-1);
int len=d[0];
if(n==2 && len%2==0){
System.out.println("3");
System.out.println((a[1]-len) + " " + (a[1]+len/2) + " " + (a[2]+len));
continue;
}
if(count>2 && d[0]!=d[count-2])
System.out.println("0");
else if(count>1 && d[count-1]>len){
if(d[count - 1] != len + len)
System.out.println("0");
else
{
System.out.println("1");
for(int i=2;i<=n;i++)
if(a[i]-a[i-1]!=len)
System.out.println((a[i-1]+len));
}
}
else{
System.out.println("2");
System.out.println((a[1]-len) + " " + (a[n]+len));
}
}
}
}/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
}
}
Space Complexity : O(1)
[forminator_quiz id="1332"]
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.