Checksum Logic

The developers 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, represented by param[i]. The secret key also has n values, and a good secret key produces more distinct values in the hash array.

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

Example
Input:
n = 3
param = [1, 2, 4]

Possible secretKey = [1, 3, 2].
Then hash = [0, 1, 2] -> 3 distinct values

Function Signature
int findHash(int param[n])

Returns
Maximum number of distinct elements in hash.

Constraints
1 ≤ n ≤ 2 × 10⁵


Solution







Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.