Interview question of SpringWorks

Problem Statement

Hashing is used to solve very complicated problems. Hashing also makes searching easy. Hashing means x % y. You have to select the integer such that when every element is modulus with that integer then the chances to easily identify every element will be maximum.

You are given a list of integers and you have to select the minimum integer from the list such that there would be as many as less collision possible. A collision occurs when elements yield the same modulus on different elements of the list.

Input Format

First-line contains N’s value, the number of elements in a list.

Second-line contains the space-separated value of array

elements.

Constraints

1<N<= 10³

• 1 <= arr[i]<= 10³

Output Format

• Print the value of X, the integer that satisfies less collision.

Evaluation Parameter

Sample Input
5

54 32 7 21 6

Sample Output

21

Explanation

Elements with a list of unique values achieved when other elements get modulus with it:

• For 54-{0, 32, 7,21,6}

For 32-{22,0,7, 21,6}

For 7-{5,4,0,6)

For 21- {12, 11,7,0,6}

• For 6-{0,2,1,3}

Among all four 54, 32, and 21 can be used to reduce collision. Among all these three elements 21 is the smallest.

EXECUTION TIME LIMIT

2 seconds