Arithmetic Progression

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:

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

Previous post Friends Ages
Next post Array Max

Leave a Reply

Your email address will not be published. Required fields are marked *