Minimum number of elements to be removed to make XOR maximum

0 0 5 minutes read

Given a number $N$ where $1\leq N\leq 10^{18}$ . The task is to find the minimum number of elements to be deleted in between $1$ to $N$ 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 $n=1$ or $n=2$ , 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 $n$ .
Let’s call this number be $a$ .
So, if $n=a$ or $n=a-1$ then we will just remove $a-1$ . Hence the answer is 1.
else if $n=a-2$ , then answer is 0. No need to remove any element.
Case 3: Otherwise, if $n$ is $even$ , then answer is 1.
else if $n$ is $odd$ , 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 code
int 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 value
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(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 value
 
def 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 Code
if __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 value
 
using 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 value
 
function 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 removed
echo removeElement($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation to 
// find minimum number of
// elements to remove to get 
// maximum XOR value
 
function 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:

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 zambiatek!