XOR máximo usando números K de 1 a n

Dado un entero positivo n y k. Encuentre xor máximo de 1 a n usando como máximo k números. X o la suma de 1 a n se define como 1 ^ 2 ^ 3 ^ … ^ n.
Ejemplos: 
 

Input :  n = 4, k = 3
Output : 7
Explanation
Maximum possible xor sum is 1 ^ 2 ^ 4 = 7.

Input : n = 11, k = 1
Output : 11
Explanation
Maximum Possible xor sum is 11.

Si tenemos k = 1, entonces la suma xor máxima posible es ‘n’ misma. Ahora, para k > 1, siempre podemos tener un número con todos sus bits establecidos hasta el bit más significativo establecido en ‘n’.

// CPP program to find max xor sum
// of 1 to n using atmost k numbers
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// To return max xor sum of 1 to n
// using at most k numbers
ll maxXorSum(ll n, ll k)
{
    // If k is 1 then maximum
    // possible sum is n
    if (k == 1)
        return n;
 
    // Finding number greater than
    // or equal to n with most significant
    // bit same as n. For example, if n is
    // 4, result is 7. If n is 5 or 6, result
    // is 7
    ll res = 1;
    while (res <= n)
        res <<= 1;
 
    // Return res - 1 which denotes
    // a number with all bits set to 1
    return res - 1;
}
 
// Driver program
int main()
{
    ll n = 4, k = 3;
    cout << maxXorSum(n, k);
    return 0;
}

// Java program to find max xor sum
// of 1 to n using atmost k numbers
public class Main {
 
    // To return max xor sum of 1 to n
    // using at most k numbers
    static int maxXorSum(int n, int k)
    {
        // If k is 1 then maximum
        // possible sum is n
        if (k == 1)
            return n;
 
        // Finding number greater than
        // or equal to n with most significant
        // bit same as n. For example, if n is
        // 4, result is 7. If n is 5 or 6, result
        // is 7
        int res = 1;
        while (res <= n)
            res <<= 1;
 
        // Return res - 1 which denotes
        // a number with all bits set to 1
        return res - 1;
    }
 
    // Driver program to test maxXorSum()
    public static void main(String[] args)
    {
        int n = 4, k = 3;
        System.out.print(maxXorSum(n, k));
    }
}

# Python3 code to find max xor sum
# of 1 to n using atmost k numbers
 
# To return max xor sum of 1 to n
# using at most k numbers
def maxXorSum( n , k ):
    # If k is 1 then maximum
    # possible sum is n
    if k == 1:
        return n
     
    # Finding number greater than
    # or equal to n with most significant
    # bit same as n. For example, if n is
    # 4, result is 7. If n is 5 or 6, result
    # is 7
    res = 1
    while res <= n:
        res <<= 1
     
    # Return res - 1 which denotes
    # a number with all bits set to 1
    return res - 1
 
# Driver code
n = 4
k = 3
print( maxXorSum(n, k) )
 
# This code is contributed by Abhishek Sharma44.

// C# program to find max xor sum
// of 1 to n using atmost k numbers
using System;
 
public class main {
 
    // To return max xor sum of 1 to n
    // using at most k numbers
    static int maxXorSum(int n, int k)
    {
        // If k is 1 then maximum
        // possible sum is n
        if (k == 1)
            return n;
 
        // Finding number greater than
        // or equal to n with most significant
        // bit same as n. For example, if n is
        // 4, result is 7. If n is 5 or 6, result
        // is 7
        int res = 1;
        while (res <= n)
            res <<= 1;
 
        // Return res - 1 which denotes
        // a number with all bits set to 1
        return res - 1;
    }
 
    // Driver program
    public static void Main()
    {
        int n = 4, k = 3;
        Console.WriteLine(maxXorSum(n, k));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find max xor sum
// of 1 to n using atmost k numbers
 
// To return max xor sum of 1 to n
// using at most k numbers
function maxXorSum($n, $k)
{
    // If k is 1 then maximum
    // possible sum is n
    if ($k == 1)
        return $n;
 
    // Finding number greater than
    // or equal to n with most
    // significant bit same as n.
    // For example, if n is 4, result
    // is 7. If n is 5 or 6, result is 7
    $res = 1;
    while ($res <= $n)
        $res <<= 1;
 
    // Return res - 1 which denotes
    // a number with all bits set to 1
    return $res - 1;
}
 
// Driver code
$n = 4;
$k = 3;
echo maxXorSum($n, $k);
 
// This code is contributed by Mithun Kumar
?>

<script>
 
// JavaScript program to find max xor sum
// of 1 to n using atmost k numbers
 
    // To return max xor sum of 1 to n
    // using at most k numbers
    function maxXorSum(n, k)
    {
        // If k is 1 then maximum
        // possible sum is n
        if (k == 1)
            return n;
   
        // Finding number greater than
        // or equal to n with most significant
        // bit same as n. For example, if n is
        // 4, result is 7. If n is 5 or 6, result
        // is 7
        let res = 1;
        while (res <= n)
            res <<= 1;
   
        // Return res - 1 which denotes
        // a number with all bits set to 1
        return res - 1;
    }
       
 
// Driver code
         
        let n = 4, k = 3;
        document.write(maxXorSum(n, k));
 
</script>

Producción : 

7

Complejidad de tiempo: O (logn)

Complejidad espacial : O(1)