Distinct Numbers

Problem Description

You are given an array of integers A having D distinct numbers. There is an operation that you can apply any number of times on the A.

In one operation, you can do A[i] = A[i] ⊕ X; where X can be any integer and ⊕ is a XOR operation.

Return the minimum number of such operations required to modify A in such a way that it only contains at most B distinct numbers.

Problem Constraints

1 <= |A| <= 10⁵
0 <= A[i] <= 10⁹

1 <= K <= 10⁵

Input Format

First argument is an array of integers A
Second argument is an integer B

Output Format

Return an integer denoting the minimum number of operations

Example Input

Input 1:

A = [1, 2, 3]
B = 2

Input 2:

A = [1, 2, 2]
B = 2

Example Output

Output 1:

Output 2:

Example Explanation

For Input 1:

A[0] ⊕ 2 = 1 ⊕ 2 = 3
A = [3, 2, 3]
So, Minimum operations = 1

For Input 2:

No operation is required

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Distinct Numbers on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Distinct Numbers

Discussion