# Arithmetic Progression

#### CONCEPTS USED:

Hashing, Basic Mathematics

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array of `N` integers, print the value of all those elements, whose indexes form an increasing `Arithmetic Progression` along with the difference in `Arithmetic Progression`. If an element occurs single time then print `0` as difference.

See original problem statement here

#### For Example:

``````Input:

N = 8
A[] = [4, 2, 4, 3, 4, 2, 4, 5]

Output:

4
2 4
3 0
4 2
5 0

Explanation:

2 is present at index 1 and 5 which forms an A.P. with common difference 4

3 is present only at index 3 which is again an A.P. with common difference 0

4 is present at index 0, 2, 4, and 6 which forms an A.P. with common difference 2

5 is present only at index 7 which is again an A.P. with common difference 0``````

#### SOLVING APPROACH:

1. It can be easily solved in `Linear Time Complexity` i.e. `O(N)` but taking additional `O(N)` space.

2. Traverse the array and keep putting the elements into a `set`.

A `set` is a data structure that contains unique elements according to data structures and algorithms.

3. Maintain two different arrays for `difference value` and `last value` of an element and keep updating them.

4. If the updated `difference value` does not matches the old value, this implies that the indices of this element are not in `Arithmetic Progression`. Therefore remove the element from the set.

5. Finally print the elements and their `difference value` from the set.

#### ILLUSTRATION:

``````A[] = [4, 2, 4, 3, 4]

i = 0
set = { }

A = 4 is not present in set, insert it
set = {4}
diff = 0
last_index = i = 0
i++;

i = 1
A = 2 is not present in set, insert it
set = {2, 4}
diff = 0
last_index = i =  1
i++;

i = 2
A = 4 is present in set, update last_index and difference
diff = i - last_index = 2 - 0 = 2
last_index = i =  2
i++;

i = 3
A = 3 is not present in set, insert it
set = {2, 3, 4}
diff = 0
last_index = i = 3
i++ ;

i = 4
A = 4 is present in set, update last_index and difference
(if updated diff is not equal to previous diff, erase this element)
diff = i - last_index = 4 - 2 = 2
last_index = i = 4

Now print all elements of set along with their differences

set = {2, 3, 4}

3   (size of set)
2 0 (diff)
3 0 (diff)
4 2 (diff)``````

#### SOLUTIONS:

```#include

int a1,a2;
int b1;
int main() {
int n,a,o=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a);
if(b1[a])
continue;
if(a1[a]) {
if(!a2[a])
a2[a]=i-a1[a];
else if(a2[a]!=i-a1[a])
{
b1[a]=1;--o;
}
}
else ++o;
a1[a]=i;
}
printf("%d\n",o);
for(int i=1;i<100001;++i)
if(a1[i]&&!b1[i])
printf("%d %d\n",i,a2[i]);
}
```
```#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll n,a;
cin>>n;
ll diff={0},last_value={0};
bool b;
set<ll>s;
memset(b,false,sizeof(b));
for(ll i=1;i<=n;i++){
cin>>a;
if(!b[a]){
s.insert(a);
b[a]=true;
}
else{
if(diff[a]&&(i!=diff[a]+last_value[a])){
s.erase(a);
}
diff[a]=i-last_value[a];
}
last_value[a]=i;
}
cout<<s.size()<<endl;
for(auto it=s.begin();it!=s.end();it++){
cout<<*it<<" "<<diff[*it]<<endl;
}
}
```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int a1[] = new int;
int a2[] = new int;
int b1[] = new int;
int n = sc.nextInt();
int a,o=0;

for(int i=1;i<=n;++i) {
a = sc.nextInt();
if(b1[a]>0)
continue;
if(a1[a]>0) {
if(a2[a] < 1)
a2[a]=i-a1[a];
else if(a2[a]!=i-a1[a])
{
b1[a]=1;--o;
}
}
else ++o;
a1[a]=i;
}
System.out.println(o);
for(int i=1;i<100001;++i)
if(a1[i]>0 && b1[i]<1)
System.out.println(i + " " + a2[i]);
}
}
```