# Arithmetic Progression

#### CONCEPTS USED:

Hashing, Basic Mathematics

#### DIFFICULTY LEVEL:

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:

It can be easily solved in

`Linear Time Complexity`

i.e.`O(N)`

but taking additional`O(N)`

space.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.Maintain two different arrays for

`difference value`

and`last value`

of an element and keep updating them.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.Finally print the elements and their

`difference value`

from the set.

#### ILLUSTRATION:

```
A[] = [4, 2, 4, 3, 4]
i = 0
set = { }
A[0] = 4 is not present in set, insert it
set = {4}
diff[4] = 0
last_index[4] = i = 0
i++;
i = 1
A[1] = 2 is not present in set, insert it
set = {2, 4}
diff[2] = 0
last_index[2] = i = 1
i++;
i = 2
A[2] = 4 is present in set, update last_index and difference
diff[4] = i - last_index[4] = 2 - 0 = 2
last_index[4] = i = 2
i++;
i = 3
A[3] = 3 is not present in set, insert it
set = {2, 3, 4}
diff[3] = 0
last_index[3] = i = 3
i++ ;
i = 4
A[4] = 4 is present in set, update last_index and difference
(if updated diff is not equal to previous diff, erase this element)
diff[4] = i - last_index[4] = 4 - 2 = 2
last_index[4] = i = 4
Now print all elements of set along with their differences
set = {2, 3, 4}
3 (size of set)
2 0 (diff[2])
3 0 (diff[3])
4 2 (diff[4])
```

#### SOLUTIONS:

#includeint a1[100001],a2[100001]; int b1[100001]; 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[100005]={0},last_value[100005]={0}; bool b[100005]; 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[100001]; int a2[] = new int[100001]; int b1[] = new int[100001]; 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]); } }