Given a positive integer n and k. Find maximum xor of 1 to n using at most k numbers. Xor sum of 1 to n is defined as 1 ^ 2 ^ 3 ^ … ^ n.
Examples :
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.
If we have k = 1 then the maximum possible xor sum is ‘n’ itself. Now for k > 1, we can always have a number with its all bits set till the most significant set bit in ‘n’.
C++
// 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 numbersll 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
// Java program to find max xor sum// of 1 to n using atmost k numberspublic 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)); }} |
Python
# 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 numbersdef 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 coden = 4k = 3print( maxXorSum(n, k) )# This code is contributed by Abhishek Sharma44. |
C#
// C# program to find max xor sum// of 1 to n using atmost k numbersusing 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// 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 numbersfunction 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?> |
Javascript
<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> |
Output
7
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!
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/maximum-xor-using-k-numbers-from-1-to-n/ […]