# Find K’th smallest number such that A + B = A | B

Given two numbers **A** and **K**, the task is to find **K’th smallest positive integer** B, such that **A + B = A | B**, where | denotes the **bitwise OR** operator.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A = 10, K = 3Output:5Explanation:K = 1, 10 + 1 = 10 | 1 = 11 K = 2, 10 + 4 = 10 | 4 = 14 K = 3, 10 + 5 = 10 | 5 = 15Input:A = 1, B = 1Output: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 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.

Below is the implementation of the above approach:

## C++

`// C++ program for the` `// above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find k'th` `// smallest number such that` `// A + B = A | B` `long` `long` `kthSmallest(` `long` `long` `a, ` `long` `long` `k)` `{` ` ` `// res will store` ` ` `// final answer` ` ` `long` `long` `res = 0;` ` ` `long` `long` `j = 0;` ` ` `for` `(` `long` `long` `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)) {` ` ` `res |= (1LL << j);` ` ` `}` ` ` `// Proceed to next bit` ` ` `j++;` ` ` `}` ` ` `return` `res;` `}` `// Driver Code` `int` `main()` `{` ` ` `long` `long` `a = 5, k = 3;` ` ` `cout << kthSmallest(a, k) << ` `"\n"` `;` ` ` `return` `0;` `}` |

## Python3

`# Python3 program for the above approach` `# Function to find k'th` `# smallest number such that` `# A + B = A | B` `def` `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)):` ` ` `res |` `=` `(` `1` `<< j)` ` ` `# Proceed to next bit` ` ` `j ` `+` `=` `1` ` ` `return` `res` `# Driver Code` `a ` `=` `5` `k ` `=` `3` `print` `(kthSmallest(a, k))` `# This code is contributed by himanshu77` |

## Javascript

`<script>` `// Javascript program for the` `// above approach` `// Function to find k'th` `// smallest number such that` `// A + B = A | B` `function` `kthSmallest(a, k)` `{` ` ` ` ` `// res will store` ` ` `// final answer` ` ` `let res = 0;` ` ` `let j = 0;` ` ` ` ` `for` `(let 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)) {` ` ` `res |= (1 << j);` ` ` `}` ` ` ` ` `// Proceed to next bit` ` ` `j++;` ` ` `}` ` ` ` ` `return` `res;` `}` `// Driver Code` ` ` ` ` `let a = 5, k = 3;` ` ` `document.write(kthSmallest(a, k));` ` ` `</script>` |

**Output:**

10

**Time Complexity:** O(log(n))

**Auxiliary Space: **O(1)