Minimum Distances Hackerrank problem solution

Minimum Distances Hackerrank

Consider an array of integers, A=[a0,a1,….,an-1]. The distance between two indices, i and j, is denoted by di,j=|i-j|.

Given A, find the minimum di,j such that ai=aj and i!=j. In other words, find the minimum distance between any pair of equal elements in the array. If no such value exists, print -1.

Note: |a| denotes the absolute value of a.

Input Format

The first line contains an integer, n, denoting the size of array A.
The second line contains n space-separated integers describing the respective elements in array A.

Constraints
1<=n<=103
1<=ai<=105
Output Format

Print a single integer denoting the minimum di,j in A; if no such value exists, print -1.

Sample Input

6
7 1 3 4 1 7
Sample Output

3

Explanation
Here, we have two options:

a1 and a4 are both 1, so d1,4=|1-4|=3.
a0 and a5 are both 7, so d0,5=|0-5|=5.
The answer is min(3,5)=3.

Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int min(int a,int b)
    {
    return a<b?a:b;
}
int main(){
    int size,d=9999;
    scanf("%d\n",&size);
    int a[1000];
    int i;
    for(i=0;i<size;i++)
        scanf("%d",&a[i]);
    int last[100000];
    for(i=0;i<100000;i++)
        last[i]=-1;
    for(i=0;i<size;i++)
        {
        if(last[a[i]]==-1) last[a[i]]=i;
        else
            {
            d=min(d,i-last[a[i]]);
            last[a[i]]=i;
        }
    }
    if(d==9999)
        printf("-1\n");
    else
        printf("%d\n",d);
}
Python 2
n = int(raw_input())
A = map(int, raw_input().split())

ans = 9999999999
for i in range(n):
    for j in range(n):
        if A[i] == A[j] and i != j:
            ans = min(ans, abs(i - j))

if ans == 9999999999:
    ans = -1
print ans
#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000+1];
#define inf 1000000000
int main() {
	cin>>n;
	for(int i = 0; i < n; i++) cin>>a[i];

	int res = inf;
	for(int i = 0; i < n; i++) 
		for(int j = 0; j < i; j++) 
			if(a[i] == a[j]) res = min(res, i - j);

	if(res == inf) res = -1;
	cout << res << endl;
	
	return 0;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.