  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Arithmetic Progression

Last Updated on March 28, 2022 by Ria Pathak ### 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.

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
using namespace std;
typedef long long int ll;
int main(){
ll n,a;
cin>>n;
ll diff={0},last_value={0};
bool b;
sets;
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<
```
```import java.util.*;
import java.io.*;

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

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ages[] = new int[n];
for(int i=0;i= ageB) continue;
if (ageA < ageB) continue;
if (ageA < 100 && 100 < ageB) continue;
ans += countA * countB;
if (ageA == ageB) ans -= countA;
}
}

System.out.println(ans);
}
}
```
```n = int(input())
l = list(map(int,input().split()))
diff = [0 for i in range(100005)]
last_value = [0 for i in range(100005)]
b = [False for i in range(100005)]
s = set()
for i in range(1,n+1):
a = l[i-1]
if not b[a]:
b[a] = True
else:
if diff[a] and i != diff[a] + last_value[a]: