Cuente pares ordenados de números positivos tales que su suma sea S y XOR sea K

Dada una suma $S$ y un número $K$ . La tarea es contar todos los pares ordenados posibles (a, b) de números positivos de modo que los dos enteros positivos a y b tengan una suma de S y un XOR bit a bit de K .

Ejemplos :

Input : S = 9, K = 5
Output : 4
The ordered pairs are  (2, 7), (3, 6), (6, 3), (7, 2)

Input : S = 2, K = 2
Output : 0
There are no such ordered pair.

Método: para dos enteros cualesquiera a y b

La suma S = a + b se puede escribir como S = (a $\oplus$ b) + (a & b)*2
Donde a $\oplus$ b es el XOR bit a bit y a & b es AND bit a bit de los dos números a y b respectivamente.

Esto se debe a que $\oplus$ es una suma binaria no portadora. Así podemos escribir a & b = (SK)/2 donde S=(a + b) y K = (a $\text{[math]}$ b) .
Si (SK) es impar o (SK) menor que 0, entonces no existe tal par ordenado.

Ahora, para cada bit , a&b $\in$ {0, 1} y (a $\oplus$ b) $\in$ {0, 1}.

Si, (a $\oplus$ b) = 0 entonces a _i = b _i , entonces tenemos una posibilidad: a _i = b _i = (a _i & b _i ).
Si (a $\oplus$ b) = 1, entonces debemos tener (a _i & b _i ) = 0 (de lo contrario, la salida es 0), y tenemos dos opciones: (a _i = 1 y b _i = 0) o (a _i = 0 y b _i = 1).

Donde a _i es el i-ésimo bit en a y b _i es el i-ésimo bit en b.
Por lo tanto, la respuesta es 2 ${^p}$ , donde $p$ es el número de bits establecidos en K.
Restaremos 2 si S y K son iguales porque a y b deben ser positivos (> 0).
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
int countPairs(int s, int K)
{
    // Check if no such pair exists
    if (K > s || (s - K) % 2) {
        return 0;
    }
 
    if ((s - K) / 2 & K) {
        return 0;
    }
 
    // Calculate set bits in K
    int setBits = __builtin_popcount(K);
 
    // Calculate pairs
    int pairsCount = pow(2, setBits);
 
    // If s = k, subtract 2 from result
    if (s == K)
        pairsCount -= 2;
 
    return pairsCount;
}
 
// Driver code
int main()
{
    int s = 9, K = 5;
 
    cout << countPairs(s, K);
 
    return 0;
}

Java

// Java program to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
 
class GFG {
 
// Function to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
    static int countPairs(int s, int K) {
        // Check if no such pair exists
        if (K > s || (s - K) % 2 ==1) {
            return 0;
        }
 
        if ((s - K) / 2 == 1 & K == 1) {
            return 0;
        }
 
        // Calculate set bits in K
        int setBits = __builtin_popcount(K);
 
        // Calculate pairs
        int pairsCount = (int) Math.pow(2, setBits);
 
        // If s = k, subtract 2 from result
        if (s == K) {
            pairsCount -= 2;
        }
 
        return pairsCount;
    }
 
    static int __builtin_popcount(int n) {
        /* Function to get no of set 
    bits in binary representation 
    of positive integer n */
 
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
 
// Driver program to test above function
    public static void main(String[] args) {
        int s = 9, K = 5;
        System.out.println(countPairs(s, K));
 
    }
 
}

Python3

# Python3 program to count ordered pairs of
# positive numbers such that their
# sum is S and XOR is K
 
# Function to count ordered pairs of
# positive numbers such that their
# sum is S and XOR is K
def countPairs(s,K):
    if(K>s or (s-K)%2==1):
        return 0
         
    # Calculate set bits in k
    setBits=(str(bin(K))[2:]).count("1")
 
    # Calculate pairs
    pairsCount = pow(2,setBits)
 
    # If s = k, subtract 2 from result
    if(s==K):
        pairsCount-=2
 
    return pairsCount
 
# Driver code
if __name__=='__main__':
    s,K=9,5
    print(countPairs(s,K))
 
# This code is contributed by
# Indrajit Sinha.

C#

// C# program to count ordered pairs
// of positive numbers such that their
// sum is S and XOR is K
using System;
                     
class GFG
{
 
// Function to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
static int countPairs(int s, int K)
{
    // Check if no such pair exists
    if (K > s || (s - K) % 2 ==1)
    {
        return 0;
    }
 
    if ((s - K) / 2 == 1 & K == 1)
    {
        return 0;
    }
 
    // Calculate set bits in K
    int setBits = __builtin_popcount(K);
 
    // Calculate pairs
    int pairsCount = (int) Math.Pow(2, setBits);
 
    // If s = k, subtract 2 from result
    if (s == K)
    {
        pairsCount -= 2;
    }
 
    return pairsCount;
}
 
static int __builtin_popcount(int n)
{
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    int count = 0;
    while (n > 0)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver Code
public static void Main()
{
    int s = 9, K = 5;
    Console.Write(countPairs(s, K));
}
}
 
// This code is contributed
// by Rajput-Ji

PHP

<?php
// PHP program to count ordered
// pairs of positive numbers such
// that their sum is S and XOR is K
 
// Function to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
function countPairs($s, $K)
{
    // Check if no such pair exists
    if ($K > $s || ($s - $K) % 2 == 1)
    {
        return 0;
    }
 
    if (($s - $K) / 2 == 1 & $K == 1)
    {
        return 0;
    }
 
    // Calculate set bits in K
    $setBits = __builtin_popcount($K);
 
    // Calculate pairs
    $pairsCount = (int)pow(2, $setBits);
 
    // If s = k, subtract 2 from result
    if ($s == $K)
    {
        $pairsCount -= 2;
    }
 
    return $pairsCount;
}
 
function __builtin_popcount($n)
{
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    $count = 0;
    while ($n > 0)
    {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}
 
// Driver Code
$s = 9; $K = 5;
echo countPairs($s, $K) . "\n";
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
 
// Javascript program to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
 
// Function to count ordered pairs of
// positive numbers such that their
// sum is S and XOR is K
function countPairs(s, K)
{
    // Check if no such pair exists
    if (K > s || (s - K) % 2) {
        return 0;
    }
 
    if (parseInt((s - K) / 2) & K) {
        return 0;
    }
 
    // Calculate set bits in K
    let setBits = __builtin_popcount(K);
 
    // Calculate pairs
    let pairsCount = Math.pow(2, setBits);
 
    // If s = k, subtract 2 from result
    if (s == K)
        pairsCount -= 2;
 
    return pairsCount;
}
 
function __builtin_popcount(n)
{
    /* Function to get no of set
    bits in binary representation
    of positive integer n */
    let count = 0;
    while (n > 0)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver code
    let s = 9, K = 5;
 
    document.write(countPairs(s, K));
 
</script>

Producción:

Complejidad de tiempo: O(log(K)), Espacio auxiliar: O (1)

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta