Find X such that most Array elements are of form (X + p*K)

Given an array arr[] and a number K, the task is to find a value X such that maximum number of array elements can be expressed in the form (X + p*K).

Note: If there are multiple possible values of X, print the minimum among them.

Examples:

Input: arr[] = {1, 3, 5, 2, 4, 6}, k = 2
Output: 1
Explanation: On choosing 1 the elements of the form 1 + 2* p are 1, 3, 5 so 3 which is the maximum count of elements of the given form and 1 is the minimum number satisfying the condition, thus the output will be 1.

Input : arr[] = {4, 10, 50}, k = 100
Output: 4
Explanation: On choosing any number we get only that number possible of that form at p = 0 so answer is minimum of the array thus 4 will be the output.

Approach: This can be solved using the following idea.

Since a number X from is to be chosen such that the most elements in the array should be of the form y = X + p * K, where K is a constant, so we can see that X is the remainder when y is divided by K.

So the number that is going to be chosen should be the remainder that is occurring maximum times when array elements are divided by K.

Follow the steps mentioned below to solve the problem:

• Initialize a hashmap m to store the frequencies of the remainders.
• Initialize res = INT_MAX to store the number to be chosen.
• Initialize max_rem to store the maximum frequency of remainders when divided by K.
• Traverse through the array and compute the remainder when divided by the K and store the frequency in the hashmap m.
• Store the maximum frequency of remainders in the max_rem variable.
• Now Traverse through the array and choose the minimum number of many elements that have the same frequency of remainders.
• Return the res.

Below is the implementation of the above approach.

Time Complexity: O(N) where N is the size of the array
Auxiliary Space: O(N) 

Given an array arr[] and a number K, the task is to find a value X such that maximum number of array elements can be expressed in the form (X + p*K).

Note: If there are multiple possible values of X, print the minimum among them.

Examples:

Input: arr[] = {1, 3, 5, 2, 4, 6}, k = 2
Output: 1
Explanation: On choosing 1 the elements of the form 1 + 2* p are 1, 3, 5 so 3 which is the maximum count of elements of the given form and 1 is the minimum number satisfying the condition, thus the output will be 1.

Input : arr[] = {4, 10, 50}, k = 100
Output: 4
Explanation: On choosing any number we get only that number possible of that form at p = 0 so answer is minimum of the array thus 4 will be the output.

Approach: This can be solved using the following idea.

Since a number X from is to be chosen such that the most elements in the array should be of the form y = X + p * K, where K is a constant, so we can see that X is the remainder when y is divided by K.

So the number that is going to be chosen should be the remainder that is occurring maximum times when array elements are divided by K.

Follow the steps mentioned below to solve the problem:

• Initialize a hashmap m to store the frequencies of the remainders.
• Initialize res = INT_MAX to store the number to be chosen.
• Initialize max_rem to store the maximum frequency of remainders when divided by K.
• Traverse through the array and compute the remainder when divided by the K and store the frequency in the hashmap m.
• Store the maximum frequency of remainders in the max_rem variable.
• Now Traverse through the array and choose the minimum number of many elements that have the same frequency of remainders.
• Return the res.

Below is the implementation of the above approach.

Time Complexity: O(N) where N is the size of the array
Auxiliary Space: O(N)