Given a number N, the task is to find four distinct numbers A, B, C, and D such that all are distinct and non-negative satisfies the condition: (((A|B)& C)^ D) = N, where ‘ | ‘ is Bitwise ‘or’, ‘&’ is Bitwise ‘and’, ‘^’ is Bitwise ‘xor’.
Examples:
Input: N = 5
Output: A = 15, B = 0, C = 16, D = 5Input: N = 16
Output: A = 0, B = 4, C = 3, D = 16A = 0 , B = 63 , C = 64 , D = 16
Naive Approach: One approach to solving the given problem is to use brute force to generate all possible combinations of four distinct non-negative integers A, B, C, and D, and check whether they satisfy the given condition (((A|B)& C)^ D) = N or not. However, this approach will not be efficient for larger values of N, and hence we need a better algorithmic approach.
Efficient Approach: This can be solved with the following idea:
- We can do this by bit manipulation concept. Let’s assume C is a number of power of two. We can make (A|B) & C equal to 0. For that A|B must be equal to (C-1). n & (n-1) = 0, when n is the power of two.
- For that, we can make A or B equal to C – 1 and another equal to 0. By doing this we get (A|B) & C = 0. Now we know a number of two numbers is equal to 0 when the number is the same, as A^A = 0; 0^A = A. So D must be equal to N.
- If N == 0 then a special case arises, then we have to find A as a power of two and B = A – 1. By that, we can find an integer X-1 where X is the power of two. for that, we can make C = X and D = 0. And we can make the answer.
Below is the implementation of the above approach :
C++
// C++ Implementation of the above approach#include <bits/stdc++.h>using namespace std;int bitcount(int n) { return (int)log2(n) + 1; }void FindSquad(int N){ // Initialized the squad // variable a, b, c, d int a, b, c, d; // Find the bit of the given number int power = bitcount(N) + 1; c = (1 << power); // Taking a = 0 a = 0; // B = C-1 by that we made // (A|B) & C == 0 b = c - 1; // Now make the D = N d = N; // For N == 0 taking the special // case which is already initialized // at explanation if (N == 0) { a = 4; b = 3; c = 8; d = 0; } // Giving the output cout << "A = " << a << " " << ", B = " << b << " " << ", C = " << c << " " << ", D = " << d << endl; return;}// Drivers codesigned main(){ int n = 5; // Calling the function findsquad FindSquad(n); return 0;} |
Java
// Java Implementation of the above approachimport java.util.*;class Main { static int bitcount(int n) { return (int)(Math.log(n) / Math.log(2)) + 1; } static void FindSquad(int N) { // Initialized the squad // variable a, b, c, d int a, b, c, d; // Find the bit of the given number int power = bitcount(N) + 1; c = (1 << power); // Taking a = 0 a = 0; // B = C-1 by that we made // (A|B) & C == 0 b = c - 1; // Now make the D = N d = N; // For N == 0 taking the special // case which is already initialized // at explanation if (N == 0) { a = 4; b = 3; c = 8; d = 0; } // Giving the output System.out.println("A = " + a + ", B = " + b + ", C = " + c + ", D = " + d); } // Drivers code public static void main(String[] args) { int n = 5; // Calling the function findsquad FindSquad(n); }}// This code is contributed by Prajwal Kandekar |
Python3
# Python Implementation of the above approachimport mathdef bitcount(n): return (int)(math.log2(n)) + 1def FindSquad(N): # Initialized the squad # variable a, b, c, d a, b, c, d = 0, 0, 0, 0 # Find the bit of the given number power = bitcount(N) + 1 c = (1 << power) # Taking a = 0 a = 0 # B = C-1 by that we made # (A|B) & C == 0 b = c - 1 # Now make the D = N d = N # For N == 0 taking the special # case which is already initialized # at explanation if (N == 0): a = 4 b = 3 c = 8 d = 0 # Giving the output print("A = ", a, ", B = ", b, ", C = ", c, ", D = ", d)# Driver codeif __name__ == "__main__": n = 5 # Calling the function findsquad FindSquad(n)# This code is contributed by Tapesh(tapeshdua420) |
C#
using System;public class Program{ static int bitcount(int n) { return (int)Math.Log(n, 2) + 1; } static void FindSquad(int N) { // Initialized the squad // variable a, b, c, d int a, b, c, d; // Find the bit of the given number int power = bitcount(N) + 1; c = (1 << power); // Taking a = 0 a = 0; // B = C-1 by that we made // (A|B) & C == 0 b = c - 1; // Now make the D = N d = N; // For N == 0 taking the special // case which is already initialized // at explanation if (N == 0) { a = 4; b = 3; c = 8; d = 0; } // Giving the output Console.WriteLine("A = {0}, B = {1}, C = {2}, D = {3}", a, b, c, d); } public static void Main(string[] args) { int n = 5; // Calling the function FindSquad FindSquad(n); }} |
Javascript
// Javascript Implementation of the above approachfunction bitCount(n) { return Math.floor(Math.log2(n)) + 1;}function findSquad(N) { let a, b, c, d; // Find the bit of the given number const power = bitCount(N) + 1; c = 1 << power; // Taking a = 0 a = 0; // B = C-1 by that we made (A|B) & C == 0 b = c - 1; // Now make the D = N d = N; // For N == 0 taking the special case if (N === 0) { a = 4; b = 3; c = 8; d = 0; } // Output the values console.log(`A = ${a}, B = ${b}, C = ${c}, D = ${d}`);}// Driver codeconst n = 5;findSquad(n); |
Output
A = 0, B = 15, C = 16, D = 5
Time Complexity: O(1)
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