Given a number 
where 
. The task is to find the minimum number of elements to be deleted in between 
to such that the XOR obtained from the remaining elements is maximum.
Examples:
Input: N = 5 Output: 2 Input: 1000000000000000 Output: 1
Approach: Considering the following cases:
Case 1: When
or
, then answer is 0. No need to remove any element.
Case 2: Now, we have to find a number which is power of 2 and greater than or equal to.
Let’s call this number be.
So, ifor
then we will just remove
. Hence the answer is 1.
else if, then answer is 0. No need to remove any element.
Case 3: Otherwise, if, then answer is 1.
else if, then answer is 2.
or 
, then answer is 0. No need to remove any element.
. 
.
or 
then we will just remove 
. Hence the answer is 1.
, then answer is 0. No need to remove any element.
, then answer is 1. 
, then answer is 2.Below is the implementation of the above approach:
C++
// C++ implementation to find minimum number of// elements to remove to get maximum XOR value#include <bits/stdc++.h>using namespace std;unsigned int nextPowerOf2(unsigned int n){ unsigned count = 0; // First n in the below condition // is for the case where n is 0 if (n && !(n & (n - 1))) return n; while (n != 0) { n >>= 1; count += 1; } return 1 << count;}// Function to find minimum number of// elements to be removed.int removeElement(unsigned int n){ if (n == 1 || n == 2) return 0; unsigned int a = nextPowerOf2(n); if (n == a || n == a - 1) return 1; else if (n == a - 2) return 0; else if (n % 2 == 0) return 1; else return 2;}// Driver codeint main(){ unsigned int n = 5; // print minimum number of elements // to be removed cout << removeElement(n); return 0;} |
Java
//Java implementation to find minimum number of//elements to remove to get maximum XOR valuepublic class GFG { static int nextPowerOf2(int n) { int count = 0; // First n in the below condition // is for the case where n is 0 if (n!=0 && (n& (n - 1))==0) return n; while (n != 0) { n >>= 1; count += 1; } return 1 << count; } //Function to find minimum number of //elements to be removed. static int removeElement(int n) { if (n == 1 || n == 2) return 0; int a = nextPowerOf2(n); if (n == a || n == a - 1) return 1; else if (n == a - 2) return 0; else if (n % 2 == 0) return 1; else return 2; } //Driver code public static void main(String[] args) { int n = 5; // print minimum number of elements // to be removed System.out.println(removeElement(n)); }} |
Python 3
# Python 3 to find minimum number # of elements to remove to get # maximum XOR valuedef nextPowerOf2(n) : count = 0 # First n in the below condition # is for the case where n is 0 if (n and not(n and (n - 1))) : return n while n != 0 : n >>= 1 count += 1 return 1 << count# Function to find minimum number # of elements to be removed. def removeElement(n) : if n == 1 or n == 2 : return 0 a = nextPowerOf2(n) if n == a or n == a - 1 : return 1 elif n == a - 2 : return 0 elif n % 2 == 0 : return 1 else : return 2 # Driver Codeif __name__ == "__main__" : n = 5 # print minimum number of # elements to be removed print(removeElement(n))# This code is contributed # by ANKITRAI1 |
C#
//C# implementation to find minimum number of//elements to remove to get maximum XOR valueusing System;public class GFG { static int nextPowerOf2(int n) { int count = 0; // First n in the below condition // is for the case where n is 0 if (n!=0 && (n& (n - 1))==0) return n; while (n != 0) { n >>= 1; count += 1; } return 1 << count; } //Function to find minimum number of //elements to be removed. static int removeElement(int n) { if (n == 1 || n == 2) return 0; int a = nextPowerOf2(n); if (n == a || n == a - 1) return 1; else if (n == a - 2) return 0; else if (n % 2 == 0) return 1; else return 2; } //Driver code public static void Main() { int n = 5; // print minimum number of elements // to be removed Console.Write(removeElement(n)); }} |
PHP
<?php// PHP implementation to find // minimum number of elements // to remove to get maximum // XOR valuefunction nextPowerOf2($n){ $count = 0; // First n in the below condition // is for the case where n is 0 if ($n && !($n & ($n - 1))) return $n; while ($n != 0) { $n >>= 1; $count += 1; } return 1 << $count;}// Function to find minimum number // of elements to be removed.function removeElement($n){ if ($n == 1 || $n == 2) return 0; $a = nextPowerOf2($n); if ($n == $a || $n == $a - 1) return 1; else if ($n == $a - 2) return 0; else if ($n % 2 == 0) return 1; else return 2;}// Driver code$n = 5;// print minimum number of // elements to be removedecho removeElement($n);// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation to // find minimum number of// elements to remove to get // maximum XOR valuefunction nextPowerOf2(n){ let count = 0; // First n in the below condition // is for the case where n is 0 if (n && !(n & (n - 1))) return n; while (n != 0) { n >>= 1; count += 1; } return 1 << count;}// Function to find minimum number of// elements to be removed.function removeElement(n){ if (n == 1 || n == 2) return 0; let a = nextPowerOf2(n); if (n == a || n == a - 1) return 1; else if (n == a - 2) return 0; else if (n % 2 == 0) return 1; else return 2;}// Driver code let n = 5; // print minimum number of elements // to be removed document.write(removeElement(n));</script> |
Output:
2
Time complexity: O(logn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
