Last Updated on March 28, 2022 by Ria Pathak

### 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.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]); }

#includeusing 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]; 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]: s.add(a) b[a] = True else: if diff[a] and i != diff[a] + last_value[a]: s.discard(a) diff[a]=i-last_value[a] last_value[a]=i print(len(s)) for it in s: print(it, diff[it])

[forminator_quiz id="405"]

This article tried to discuss **Hashing, Basic Mathematics**. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing, Basic Mathematics you can check out MYCODE | Competitive Programming.