Encuentre el triplete A, B, C que tiene AND bit a bit de OR bit a bit entre sí como K

Dado un entero K , la tarea es encontrar tres enteros distintos A, B y C tales que ( A ∣ B ) & ( B ∣ C ) & ( C ∣ A ) = K , donde   |  y & denota operación OR bit a bit y AND bit a bit respectivamente. Si hay varias soluciones, puede imprimir cualquiera de ellas.

Ejemplos :

Entrada : K = 3
Salida : 1 2 3
Explicación : ( 1 ∣ 2 ) & ( 2 ∣ 3 ) & ( 3 ∣ 1 ) = 3 & 3 & 3 = 3  

Entrada : K = 13
Salida : 6 9 13

Enfoque ingenuo : Un enfoque de fuerza bruta consiste en ejecutar tres bucles anidados y encontrar los tres enteros que satisfacen la expresión anterior. 

Complejidad de Tiempo: O(K ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente : este problema se puede resolver con base en la siguiente observación:

Cada conjunto de bits de K debe estar presente en (A|B), (B|C) y (A|C), lo que implica que cada conjunto de bits de K debe estar presente en al menos 2 de A, B y C.
Entonces, haga dos números iguales a K y el otro 0. Para hacer que los dos números sean distintos, agregue una potencia mayor de 2 (que es mayor que K) a cualquiera de ellos.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Haz que A y B sean iguales a K y C = 0.
• Ahora agregue una potencia mayor de 2 (que es mayor que K) a B [Aquí usando 2 ²⁷ ].
• Imprime los valores de A, B y C.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print three integers
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
    cout << K << " " << K + (1 << 27)
         << " " << 0 << endl;
}
 
// Driver Code
int main()
{
    int K = 3;
 
    // Function call
    printABC(K);
    return 0;
}

// Java program to implement the approach
import 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 program to implement the approach
 
# function to print three integers
def 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 Code
K = 3
 
# Function Call
printABC(K)
 
# This code is contributed by phasing17

// C# program to implement the approach
using 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.

<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

Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)