Given the numbers a and k, the task is to find the k’th smallest value for b such that a + b = a | b, where ‘|’ denotes the bitwise OR operator. The maximum value of a and k can be 
.
Examples:
Input: a = 10, k = 3 Output: 5 Numbers satisfying the condition 5 + b = 5 | b are 1, 4, 5, etc. Since 3rd smallest value for b is required, hence b = 5. Input: a = 1, k = 1 Output: 2 Numbers satisfying the condition 1 + b = 1 | b are 2, 4, 6, etc. Since 1st smallest value for b is required, hence b = 2.
Approach:
- b is a solution of the given equation if and only if b has 0 in all positions where a has 1 (in binary notation).
- So, we need to determine the bit of b for positions where a has 0. Let, if a = 10100001 then the last eight digits of b must be b = 0*0****0, where ‘*’ denotes either 0 or 1. Any replacement of all ‘*’ by 0 or 1 gives us a solution.
- The k-th smallest number will be received by replacing all ‘*’ in y by digits of the binary representation of the number k.
- As the maximum value of a and k is
, so checking up to 32 positions in binary representation is enough to get the correct answer for the given equation.
Below is the implementation of the above approach:
CPP
// C++ program to find k'th smallest value for b// such that a + b = a | b#include <bits/stdc++.h>using namespace std;#define ll long long// Function to find// the kth smallest value for bll kthSmallest(ll a, ll k){ // res will store final answer ll res = 0; ll j = 0; for (ll i = 0; i < 32; i++) { // skip when j'th position // has 1 in binary representation // as in res, j'th position will be 0. while (j < 32 && (a & (1 << j))) // j'th bit is set j++; // if i'th bit of k is 1 // and i'th bit of j is 0 // then set i'th bit in res. if (k & (1 << i)) // i'th bit is set res |= (1LL << j); // proceed to next bit j++; } return res;}// Driver Codeint main(){ ll a = 10, k = 3; cout << kthSmallest(a, k) << "\n"; return 0;} |
Java
// Java program to find k'th smallest value for b// such that a + b = a | bclass GFG{ // Function to find // the kth smallest value for b static int kthSmallest(int a, int k) { // res will store final answer int res = 0; int j = 0; for (int i = 0; i < 32; i++) { // skip when j'th position // has 1 in binary representation // as in res, j'th position will be 0. while (j < 32 && (a & (1 << j)) > 0) // j'th bit is set j++; // if i'th bit of k is 1 // and i'th bit of j is 0 // then set i'th bit in res. if ((k & (1 << i)) > 0) // i'th bit is set res |= (1 << j); // proceed to next bit j++; } return res; } // Driver Code public static void main(String[] args) { int a = 10, k = 3; System.out.print(kthSmallest(a, k) + "\n"); }}// This code is contributed by Rajput-Ji |
Python
# Python3 program to find k'th smallest value for b# such that a + b = a | b# Function to find# the kth smallest value for bdef kthSmallest(a, k): # res will store final answer res = 0 j = 0 for i in range(32): # skip when j'th position # has 1 in binary representation # as in res, j'th position will be 0. while (j < 32 and (a & (1 << j))): # j'th bit is set j += 1 # if i'th bit of k is 1 # and i'th bit of j is 0 # then set i'th bit in res. if (k & (1 << i)): # i'th bit is set res |= (1 << j) # proceed to next bit j += 1 return res# Driver Codea = 10k = 3print(kthSmallest(a, k))# This code is contributed by mohit kumar 29 |
C#
// C# program to find k'th smallest value for b// such that a + b = a | busing System;class GFG{ // Function to find // the kth smallest value for b static int kthSmallest(int a, int k) { // res will store final answer int res = 0; int j = 0; for (int i = 0; i < 32; i++) { // skip when j'th position // has 1 in binary representation // as in res, j'th position will be 0. while (j < 32 && (a & (1 << j)) > 0) // j'th bit is set j++; // if i'th bit of k is 1 // and i'th bit of j is 0 // then set i'th bit in res. if ((k & (1 << i)) > 0) // i'th bit is set res |= (1 << j); // proceed to next bit j++; } return res; } // Driver Code public static void Main() { int a = 10, k = 3; Console.WriteLine(kthSmallest(a, k)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to find k'th smallest value for b// such that a + b = a | b// Function to find// the kth smallest value for bfunction kthSmallest(a, k){ // res will store final answer var res = 0; var j = 0; for (var i = 0; i < 32; i++) { // skip when j'th position // has 1 in binary representation // as in res, j'th position will be 0. while (j < 32 && (a & (1 << j))) // j'th bit is set j++; // if i'th bit of k is 1 // and i'th bit of j is 0 // then set i'th bit in res. if (k & (1 << i)) // i'th bit is set res |= (1 << j); // proceed to next bit j++; } return res;}// Driver Codevar a = 10, k = 3;document.write( kthSmallest(a, k));</script> |
Output:
5
Time Complexity: O(N)
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!
Share your thoughts in the comments
