Arithmetic Progression

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:

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[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:

#include 

int 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
    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];
        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])

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.