How should I practice Find Hash?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Find Hash associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Find Hash

Learn this problem

● MediumAmazonNEW GRADOA

See Amazon hiring insights

Problem statement

The developers at AWS IAM are designing a new checksum logic for an authentication module. The checksum is calculated as an array hash where hash[i] = secretKey[i] % param[i]. There are n parameters for the checksum, where the ith parameter is represented by param[i]. The secret key consists of n values, with the ith value denoted as secretKey[i].

A good secret key is one that results in more distinct values in the hash array.

Given the array param of size n, determine the maximum number of possible distinct values in the hash array by selecting an appropriate secretKey.

Function

findHash(param: int[]) → int

Complete the function findHash in the editor.

findHash has the following parameter:

int param[n]: the different parameters needed for the checksum logic

Returns

int: the maximum number of distinct elements possible in hash.

Examples

Example 1

param = [1, 2, 4]return = 3

You can choose secretKey = [1, 3, 2], resulting in the hash array [0, 1, 2], which consists of 3 distinct elements.

Example 2

param = [1, 1, 1]return = 1

If we set secretKey = [1, 2, 3], we get hash = [0, 0, 0], resulting in only one unique value, which is 0. Therefore, the answer is 1.

Constraints

1 ≤ n ≤ 2 * 10^5
1 ≤ param[i] ≤ 10^9