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 Bvoid 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 codeint main(){ int N = 5; findAB(N); return 0;} |
Java
// Java implementation of the approachimport 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 approachMAX = 32# Function to find A and Bdef 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 codeN = 5;findAB(N);# This code is contributed by phasing17 |
C#
// C# implementation of the approachusing 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 approachlet MAX = 32// Function to find A and Bfunction 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 codelet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
