Given an integer K, the task is to find three distinct integers A, B and C such that ( A ∣ B ) & ( B ∣ C ) & ( C ∣ A ) = K, where | and & denotes bitwise OR and bitwise AND operation respectively. If there are multiple solutions, you may print any of them.
Examples:
Input: K = 3
Output: 1 2 3
Explanation: ( 1 ∣ 2 ) & ( 2 ∣ 3 ) & ( 3 ∣ 1 ) = 3 & 3 & 3 = 3Input: K = 13
Output: 6 9 13
Naive Approach: A brute force approach is to run three nested loops and find all the three integer which satisfy the above expression .
Time Complexity: O(K3)
Auxiliary Space: O(1)
Efficient Approach: This problem can be solved based on the following observation:
Every set bit of K must be present in (A|B), (B|C) and (A|C) which implies that every set bit of K must be present in at least 2 of A, B and C.
So, make two numbers same as K and the other 0. To make the two numbers distinct add a larger power of 2 (which is greater than K) to any of them.
Follow the steps mentioned below to solve the problem:
- Make A and B equal to K and C = 0.
- Now add a higher power of 2(which is greater than K) to B [Here using 227].
- Print the values of A, B and C.
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to print three integersvoid printABC(int K){ // One of them are equal to zero // and rest two are equivalent // to X itself but to make // A!=B add a larger power of 2 to B cout << K << " " << K + (1 << 27) << " " << 0 << endl;}// Driver Codeint main(){ int K = 3; // Function call printABC(K); return 0;} |
Java
// Java program to implement the approachimport java.io.*;public class GFG { // function to print three integers static void printABC(int K) { // One of them are equal to zero // and rest two are equivalent // to X itself but to make // A!=B add a larger power of 2 to B System.out.println(K + " " + (K + (1 << 27)) + " " + 0); } // Driver Code public static void main(String[] args) { int K = 3; // Function Call printABC(K); }}// This code is contributed by phasing17 |
Python3
# Python3 program to implement the approach# function to print three integersdef printABC(K): # one of them is equal to zero # and the rest two are equivalent to X # itself but to make # A != B add a larger power of 2 to B print(K, K + (1 << 27), 0)# Driver CodeK = 3# Function CallprintABC(K)# This code is contributed by phasing17 |
C#
// C# program to implement the approachusing System;class GFG { // Function to print three integers static void printABC(int K) { // One of them are equal to zero // and rest two are equivalent // to X itself but to make // A!=B add a larger power of 2 to B Console.WriteLine(K + " " + (K + (1 << 27)) + " " + 0); } // Driver Code public static void Main() { int K = 3; // Function call printABC(K); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to implement the approach // Function to print three integers const printABC = (K) => { // One of them are equal to zero // and rest two are equivalent // to X itself but to make // A!=B add a larger power of 2 to B document.write(`${K} ${K + (1 << 27)} ${0}<br/>`); } // Driver Code let K = 3; // Function call printABC(K);// This code is contributed by rakeshsahni</script> |
3 134217731 0
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
