# K-th smallest positive integer having sum with given number equal to bitwise OR with given number

Given two positive integers **X **and** K**, the task is to find the **K**-th smallest positive integer **Y, **such that **X + Y = X | Y**, where | denotes the __bitwise OR operation.__

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:X = 5, K = 1Output:2Explanation:The first number is 2 as (2 + 5 = 2 | 5 )

Input:X = 5, K = 5Output:18Explanation:The list of correct values is 2, 8, 10, 16, 18. The 5th number is this list is 18

**Approach: **Given problem can be solved** **following the below mentioned steps:

- Let the final value be
**Y**. From theit is known that__properties of bitwise operations,__**X + Y = X & Y + X | Y**, where & is a bitwise AND of two numbers - For the equation in the problem statement to be true, the value of
**X & Y**must be 0 - So for all positions, if the ith bit is ON in
**X**then it must be OFF for all possible solutions of Y - For instance, if
**X**= 1001101001 in binary (617 in decimal notation), then the last ten digits of y must be**Y**= 0**00*0**0, where ‘*’ denotes either zero or one. Also, we can pad any number of any digits to the beginning of the number, since all higher bits are zeroes - So the final solution will be to treat all the positions where the bit can be 0 or 1 as a sequence from left to right and find the binary notation of
**K**. - Fill all positions according to the binary notation of
**K**

Below is the implementation of the above approach:

## C++

`// C++ implementation for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to calculate K-th smallest` `// solution(Y) of equation X+Y = X|Y` `long` `long` `KthSolution(` `long` `long` `X, ` `long` `long` `K)` `{` ` ` `// Initialize the variable` ` ` `// to store the answer` ` ` `long` `long` `ans = 0;` ` ` `for` `(` `int` `i = 0; i < 64; i++) {` ` ` `// The i-th bit of X is off` ` ` `if` `(!(X & (1LL << i))) {` ` ` `// The i-bit of K is on` ` ` `if` `(K & 1) {` ` ` `ans |= (1LL << i);` ` ` `}` ` ` `// Divide K by 2` ` ` `K >>= 1;` ` ` `// If K becomes 0 then break` ` ` `if` `(!K) {` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `long` `long` `X = 5, K = 5;` ` ` `cout << KthSolution(X, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to calculate K-th smallest` ` ` `// solution(Y) of equation X+Y = X|Y` ` ` `static` `long` `KthSolution(` `long` `X, ` `long` `K)` ` ` `{` ` ` ` ` `// Initialize the variable` ` ` `// to store the answer` ` ` `long` `ans = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < ` `64` `; i++) {` ` ` `// The i-th bit of X is off` ` ` `if` `((X & (` `1` `<< i)) == ` `0` `) {` ` ` `// The i-bit of K is on` ` ` `if` `((K & ` `1` `) > ` `0` `) {` ` ` `ans |= (` `1` `<< i);` ` ` `}` ` ` `// Divide K by 2` ` ` `K >>= ` `1` `;` ` ` `// If K becomes 0 then break` ` ` `if` `(K == ` `0` `) {` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `long` `X = ` `5` `, K = ` `5` `;` ` ` `System.out.println(KthSolution(X, K));` ` ` `}` `}` `// This code is contributed by sanjoy_62.` |

## Python3

`# python implementation for the above approach` `# Function to calculate K-th smallest` `# solution(Y) of equation X+Y = X|Y` `def` `KthSolution(X, K):` ` ` `# Initialize the variable` ` ` `# to store the answer` ` ` `ans ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, ` `64` `):` ` ` `# The i-th bit of X is off` ` ` `if` `(` `not` `(X & (` `1` `<< i))):` ` ` `# The i-bit of K is on` ` ` `if` `(K & ` `1` `):` ` ` `ans |` `=` `(` `1` `<< i)` ` ` `# Divide K by 2` ` ` `K >>` `=` `1` ` ` `# If K becomes 0 then break` ` ` `if` `(` `not` `K):` ` ` `break` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `X ` `=` `5` ` ` `K ` `=` `5` ` ` `print` `(KthSolution(X, K))` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# implementation for the above approach` `using` `System;` `class` `GFG ` `{` ` ` ` ` `// Function to calculate K-th smallest` ` ` `// solution(Y) of equation X+Y = X|Y` ` ` `static` `long` `KthSolution(` `long` `X, ` `long` `K)` ` ` `{` ` ` `// Initialize the variable` ` ` `// to store the answer` ` ` `long` `ans = 0;` ` ` `for` `(` `int` `i = 0; i < 64; i++) {` ` ` `// The i-th bit of X is off` ` ` `if` `((X & (1LL << i)) == 0) {` ` ` `// The i-bit of K is on` ` ` `if` `((K & 1) > 0) {` ` ` `ans |= (1LL << i);` ` ` `}` ` ` `// Divide K by 2` ` ` `K >>= 1;` ` ` `// If K becomes 0 then break` ` ` `if` `(K == 0) {` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `long` `X = 5, K = 5;` ` ` `Console.Write(KthSolution(X, K));` ` ` `}` `}` `// This code is contributed by ukasp.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to calculate K-th smallest` ` ` `// solution(Y) of equation X+Y = X|Y` ` ` `function` `KthSolution(X, K)` ` ` `{` ` ` ` ` `// Initialize the variable` ` ` `// to store the answer` ` ` `let ans = 0;` ` ` `for` `(let i = 0; i < 64; i++) {` ` ` `// The i-th bit of X is off` ` ` `if` `(!(X & (1 << i))) {` ` ` `// The i-bit of K is on` ` ` `if` `(K & 1) {` ` ` `ans |= (1 << i);` ` ` `}` ` ` `// Divide K by 2` ` ` `K >>= 1;` ` ` `// If K becomes 0 then break` ` ` `if` `(!K) {` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `let X = 5, K = 5;` ` ` `document.write(KthSolution(X, K));` ` ` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

18

**Time Complexity: **O(log(N))**Auxiliary Space: **O(1)