Find two integers A and B such that A ^ N = A + N and B ^ N = B + N

0 0 5 minutes read

Given a non-negative integer N, the task is to find two integers A (greatest integer smaller than N) and (smallest integer greater than N) such that A + N = A ^ N and B + N = B ^ N
Examples:

Input: N = 5
Output: A = 2 and B = 8
2 + 8 = 2 ^ 8 = 10
Input: N = 10
Output: A = 5 and B = 16
5 + 16 = 5 ^ 16 = 21

Approach: Lets find A and B independently. To solve this problem we have to use the property, x + y = x^y + 2 * (x & y)
Since the problem states that xor sum is equal to the given sum which implies that their AND must be 0.

Finding A: N can be represented as a series of bits of 0 and 1. To find A we will first have to find the most significant bit of N which is set. Since A & N = 0, The places where N has set bit, for that places we will make bits of A as unset and for the places where N has unset bit, we will make that bit set for A as we want to maximize A. This we will do for all the bits from most significant to the least significant. Hence we will get our A.
Finding B: Finding B is easy. Let i be the position of the leftmost set bit in 1. We want B to be greater than N, also we want B & N =0. Hence using these two facts B will be always (1<< (i+1)).

Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 32
 
// Function to find A and B
void findAB(int N)
{
    bitset<MAX> arr(N), brr(N);
 
    // To store the leftmost set bit in N
    int leftsetN = -1;
    for (int i = MAX - 1; i >= 0; --i) {
        if (arr[i] == 1) {
            leftsetN = i;
            break;
        }
    }
 
    // To store the value of A
    int A = 0;
    for (int i = leftsetN; i >= 0; --i) {
 
        // If the bit is unset in N
        // then  we will set it in A
        if (arr[i] == 0) {
            A |= (1 << i);
        }
    }
 
    // To store the value of B
    int B = 0;
 
    // B will be (1 << (leftsetN + 1))
    B = 1 << (leftsetN + 1);
 
    // Print the values of A and B
    cout << "A = " << A << " and B = " << B;
}
 
// Driver code
int main()
{
    int N = 5;
 
    findAB(N);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
    static int MAX = 32;
 
    // Function to reverse string
    static String Reverse(String s)
    {
   
        StringBuilder rev = new StringBuilder();
   
        // append a string into StringBuilder rev
        rev.append(s);
   
        // reverse StringBuilder rev
        rev.reverse();
         
        return rev.toString();
   
    }
 
    // Function to find A and B
    static void findAB(int N)
    {
        // Creating a bitset
        BitSet arr = BitSet.valueOf(new long[]{N});
     
        // To store the leftmost set bit in N
        int leftsetN = -1;
        for (int i = 63; i >= 0; --i) {
            if (arr.get(i)) {
                leftsetN = i;
                break;
            }
        }
 
        // To store the value of A
        int A = 0;
        for (int i = leftsetN; i >= 0; --i) {
 
            // If the bit is unset in N
            // then  we will set it in A
            if (!arr.get(i)) {
                A |= (1 << i);
            }
        }
 
        // To store the value of B
        int B = 0;
 
        // B will be (1 << (leftsetN + 1))
        B = 1 << (leftsetN + 1);
 
        // Print the values of A and B
        System.out.println("A = " + A + " and B = " + B);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 5;
        findAB(N);
    }
}
 
// This code is contributed by phasing17.

Python3

# Python implementation of the approach
MAX = 32
 
# Function to find A and B
def findAB(N):
    arr = bin(N)[2::]
    arr = "0" * (MAX - len(arr)) + arr
    arr = arr[::-1]
 
    # To store the leftmost set bit in N
    leftsetN = -1;
    for i in range(MAX - 1, -1, -1):
        if (arr[i] == '1'): 
            leftsetN = i;
            break;
 
    # To store the value of A
    A = 0;
    for i in range(leftsetN, -1, -1):
 
        # If the bit is unset in N
        # then  we will set it in A
        if (arr[i] == '0') :
            A |= (1 << (i));
         
    # To store the value of B
    B = 0;
 
    # B will be (1 << (leftsetN + 1))
    B = 1 << ((leftsetN) + 1);
 
    # Print the values of A and B
    print("A =", A, "and B =", B);
 
# Driver code
N = 5;
findAB(N);
 
# This code is contributed by phasing17

C#

// C# implementation of the approach
using System;
using System.Collections.Specialized;
using System.Collections.Generic;
 
class GFG {
    static int MAX = 32;
 
    // Function to reverse string
    static string Reverse(string s)
    {
        char[] charArray = s.ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
 
    // Function to find A and B
    static void findAB(int N)
    {
        BitVector32 arr = new BitVector32(N);
        string arrs = arr.ToString();
        arrs
            = Reverse(arrs.Substring(arrs.Length - 33, 32));
 
        // To store the leftmost set bit in N
        int leftsetN = -1;
        for (int i = MAX - 1; i >= 0; --i) {
            if (arrs[i] == '1') {
                leftsetN = i;
                break;
            }
        }
 
        // To store the value of A
        int A = 0;
        for (int i = leftsetN; i >= 0; --i) {
 
            // If the bit is unset in N
            // then  we will set it in A
            if (arrs[i] == '0') {
                A |= (1 << i);
            }
        }
 
        // To store the value of B
        int B = 0;
 
        // B will be (1 << (leftsetN + 1))
        B = 1 << (leftsetN + 1);
 
        // Print the values of A and B
        Console.WriteLine("A = " + A + " and B = " + B);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int N = 5;
        findAB(N);
    }
}

Javascript

// JS implementation of the approach
 
let MAX = 32
 
// Function to find A and B
function findAB(N)
{
    let arr = N.toString(2);
    arr = "0".repeat(MAX - arr.length) + arr;
    arr = arr.split("");
    arr.reverse()
 
    // To store the leftmost set bit in N
    let leftsetN = -1;
    for (let i = MAX - 1; i >= 0; --i) {
        if (arr[i] == '1') {
            leftsetN = i;
            break;
        }
    }
     
 
    // To store the value of A
    let A = 0;
    for (let i = leftsetN; i >= 0; --i) {
 
        // If the bit is unset in N
        // then  we will set it in A
        if (arr[i] == '0') {
            A |= (1 << (i));
        }
    }
 
    // To store the value of B
    let B = 0;
 
    // B will be (1 << (leftsetN + 1))
    B = 1 << ((leftsetN) + 1);
 
    // Print the values of A and B
    console.log("A = " + A + " and B = " + B);
}
 
 
// Driver code
let N = 5;
findAB(N);
 
 
// This code is contributed by phasing17

Output:

A = 2 and B = 8

Time Complexity: O(MAX)

Auxiliary Space: O(N)

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 zambiatek!