GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 2 November 2022

[Solution] One-XOR Deletions CodeChef Solution




Problem

Chef has with him an array A of length N. In one move, he can delete any element from A.

Find the minimum number of deletions Chef must make so that the following condition holds:

  • Let B denote the resulting array, and M be the length of B.
  • Then, B_i \oplus B_j \leq 1 for every 1 \leq i, j \leq M.

Here, \oplus denotes the bitwise XOR operation.

For example, [3, 3, 3] and [6, 7, 6, 7] are valid final arrays, while [1, 2] and [6, 7, 8] are not (because 1 \oplus 2 = 3 and 7\oplus 8 = 15, respectively).

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer N, denoting the length of array A.
    • The second line contains N space-separated integers A_1, A_2, \ldots, A_N — the elements of array A.

Output Format

For each test case, output on a new line the answer: the minimum number of deletions required so that the given condition is satisfied.


Explanation:

Test case 1: The given array already satisfies the condition, no deletions need to be done.

Test case 2: Chef can delete both the 3's to make the array [4, 4, 4], which satisfies the condition.

Test case 3: Chef can use three moves as follows:

  • Delete the 1, the array is now [2, 3, 4, 0].
  • Delete the 4, the array is now [2, 3, 0].
  • Delete the 0, the array is now [2, 3] which satisfies the condition.

It can be verified that using two or less deletions cannot give an array that satisfies the condition.

No comments:

Post a Comment