Cuente los pares hasta N que tengan una suma igual a su XOR

Dado un número entero N , la tarea es contar el número de pares (X, Y) tales que X + Y = X ^ Y y X + Y ≤ N . 
Nota: ^ denota Bitwise xor .

Ejemplos:

Entrada: N = 3
Salida: 9
Explicación: Los pares que cumplen las condiciones dadas son {{0, 0}, {0, 1}, {1, 0}, {0, 2}, {2, 0}, {3 , 0}, {0, 3}, {2, 1}, {1, 2}}

Entrada: N = 10
Salida: 37

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles (X, Y) y verificar si las condiciones X + Y = X ^ Y y X + Y ≤ N se cumplen o no. 

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

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que X+Y ≥ X ^ Y para cualquier valor de X e Y. Considere la representación binaria de X e Y. Sean bit(X, pos) y bit(Y, pos) los bits correspondientes a X e Y en alguna posición fija pos . La condición X+Y = X^Y  solo se cumplirá si { bit(X, pos), bit(Y, pos)} ∈ {{1, 0}, {0, 1}, {0, 0}} . En otras palabras, tanto X como Yno puede tener bits establecidos en las mismas posiciones.

En el enfoque eficiente, el problema se puede resolver utilizando Programación Dinámica . Los problemas tienen subproblemas superpuestos y una subestructura óptima. Los subproblemas se almacenan en una tabla dp[][] usando memoization donde dp[i][bound] almacena la respuesta desde la ‘i’ésima posición hasta el final y el límite es una variable booleana para asegurar que la suma de números no exceder n 

• Convierta el límite N en su representación binaria . Almacene la representación binaria en una string, digamos S , de modo que sea suficiente iterar solo sobre la longitud de la string y no el límite real.
• Defina una función recursiva IsSumEqualsXor(i,bound) realizando los siguientes pasos.
  • Verifique los casos base , si i == longitud de S , devuelva 1 , ya que se ha formado un par válido.
  • Si el resultado del estado dp[i][bound] ya se calculó, devuelva el estado dp[i][bound] .
  • En la posición actual i , cualquiera de los tres pares entre {{0, 0}, {0, 1}, {1, 0}} se puede asignar al verificar algunas condiciones. Están
    • Si el límite es verdadero y el carácter actual en S , es decir , S[i] es ‘0’ , entonces, solo {0, 0} se puede colocar como un par válido en la posición actual. Eso se hace para asegurar que la suma no exceda N .
    • De lo contrario, se puede colocar cualquier par entre {{0, 0}, {0, 1}, {1, 0}} y el límite se establece en verdadero o falso según corresponda.
  • Después de colocar un par válido en la posición actual, llame recursivamente a la función IsSumEqualsXor para el elemento en el índice (i + 1).
  • Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// 2D array for memoization
int dp[1000][2];
 
// Recursive Function to count pairs
// (x, y) such that x+y = x^y
int IsSumEqualsXor(int i, int n,
                   bool bound, string& s)
{
    // If the string is traversed completely
    if (i == n)
        return 1;
 
    // If the current subproblem
    // is already calculated
    if (dp[i][bound] != -1)
        return dp[i][bound];
 
    int ans = 0;
 
    // If bound = 1 and  s[i] == '0',
    // only (0, 0) can be placed
    if (bound and s[i] == '0') {
        ans = IsSumEqualsXor(i + 1, n, 1, s);
    }
 
    // Otherwise
    else {
        // Placing (0, 1) and (1, 0) are
        // equivalent. Hence, multiply by 2.
        ans = 2
              * IsSumEqualsXor(i + 1, n,
                               bound & (s[i] == '1'), s);
 
        // Place (0, 0) at the current position.
        ans += IsSumEqualsXor(i + 1, n, 0, s);
    }
 
    // Return the answer
    return dp[i][bound] = ans;
}
 
// Utility Function to convert N
// to its binary representation
string convertToBinary(int n)
{
    string ans;
    while (n) {
 
        char rem = char(n % 2 + '0');
        ans.push_back(rem);
        n /= 2;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
 
// Function to count pairs (x, y)
// such that x + y = x^y
void IsSumEqualsXorUtil(int N)
{
    // Convert the number to
    // equivalent binary representation
    string s = convertToBinary(N);
 
    // Initialize dp array with -1.
    memset(dp, -1, sizeof dp);
 
    // Print answer returned by recursive function
    cout << IsSumEqualsXor(0, s.size(), 1, s) << endl;
}
 
// Driver code
int main()
{
    // Input
    int N = 10;
 
    // Function call
    IsSumEqualsXorUtil(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// 2D array for memoization
static int [][]dp = new int[1000][2];
 
// Recursive Function to count pairs
// (x, y) such that x+y = x^y
static int IsSumEqualsXor(int i, int n,
                   int bound, char[] s)
{
    // If the String is traversed completely
    if (i == n)
        return 1;
 
    // If the current subproblem
    // is already calculated
    if (dp[i][bound] != -1)
        return dp[i][bound];
 
    int ans = 0;
 
    // If bound = 1 and  s[i] == '0',
    // only (0, 0) can be placed
    if (bound!=0 && s[i] == '0') {
        ans = IsSumEqualsXor(i + 1, n, 1, s);
    }
 
    // Otherwise
    else {
        // Placing (0, 1) and (1, 0) are
        // equivalent. Hence, multiply by 2.
        ans = 2
              * IsSumEqualsXor(i + 1, n,
                               bound!=0 & (s[i] == '1')?1:0, s);
 
        // Place (0, 0) at the current position.
        ans += IsSumEqualsXor(i + 1, n, 0, s);
    }
 
    // Return the answer
    return dp[i][bound] = ans;
}
static String reverse(String input) {
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}
// Utility Function to convert N
// to its binary representation
static String convertToBinary(int n)
{
    String ans="";
    while (n>0) {
 
        char rem = (char)(n % 2 + '0');
        ans+=(rem);
        n /= 2;
    }
    ans = reverse(ans);
    return ans;
}
 
// Function to count pairs (x, y)
// such that x + y = x^y
static void IsSumEqualsXorUtil(int N)
{
    // Convert the number to
    // equivalent binary representation
    String s = convertToBinary(N);
 
    // Initialize dp array with -1.
    for(int i = 0; i < dp.length; i++)
    {
        for (int j = 0; j < dp[0].length; j++) {
            dp[i][j] = -1;
        }
    }
 
    // Print answer returned by recursive function
    System.out.print(IsSumEqualsXor(0, s.length(), 1, s.toCharArray()) +"\n");
}
 
// Driver code
public static void main(String[] args)
{
    // Input
    int N = 10;
 
    // Function call
    IsSumEqualsXorUtil(N);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# 2D array for memoization
dp = [[-1 for i in range(2)]
          for j in range(1000)]
 
# Recursive Function to count pairs
# (x, y) such that x+y = x^y
def IsSumEqualsXor(i, n, bound, s):
     
    # If the string is traversed completely
    if (i == n):
        return 1
 
    # If the current subproblem
    # is already calculated
    if (dp[i][bound] != -1):
        return dp[i][bound]
 
    ans = 0
 
    # If bound = 1 and  s[i] == '0',
    # only (0, 0) can be placed
    if (bound and s[i] == '0'):
        ans = IsSumEqualsXor(i + 1, n, 1, s)
 
    # Otherwise
    else:
         
        # Placing (0, 1) and (1, 0) are
        # equivalent. Hence, multiply by 2.
        ans = 2 * IsSumEqualsXor(
            i + 1, n, bound & (s[i] == '1'), s)
 
        # Place (0, 0) at the current position.
        ans += IsSumEqualsXor(i + 1, n, 0, s)
         
    dp[i][bound] = ans
 
    # Return the answer
    return ans
 
# Utility Function to convert N
# to its binary representation
def convertToBinary(n):
     
    ans = []
     
    while (n):
        rem = chr(n % 2 + 48)
        ans.append(rem)
        n //= 2
         
    ans = ans[::-1]
    return ans
 
# Function to count pairs (x, y)
# such that x + y = x^y
def IsSumEqualsXorUtil(N):
     
    # Convert the number to
    # equivalent binary representation
    s = convertToBinary(N)
 
    # Print answer returned by recursive function
    print(IsSumEqualsXor(0, len(s), 1, s))
 
# Driver code
if __name__ == '__main__':
     
    # Input
    N = 10
     
    # Function call
    IsSumEqualsXorUtil(N)
     
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG{
 
// 2D array for memoization
static int [,]dp = new int[1000, 2];
 
// Recursive Function to count pairs
// (x, y) such that x+y = x^y
static int IsSumEqualsXor(int i, int n,
                          int bound, char[] s)
{
     
    // If the String is traversed completely
    if (i == n)
        return 1;
 
    // If the current subproblem
    // is already calculated
    if (dp[i,bound] != -1)
        return dp[i,bound];
 
    int ans = 0;
 
    // If bound = 1 and  s[i] == '0',
    // only (0, 0) can be placed
    if (bound != 0 && s[i] == '0')
    {
        ans = IsSumEqualsXor(i + 1, n, 1, s);
    }
 
    // Otherwise
    else
    {
         
        // Placing (0, 1) and (1, 0) are
        // equivalent. Hence, multiply by 2.
        ans = 2 * IsSumEqualsXor(i + 1, n,
                                 bound != 0 &
                                 (s[i] == '1') ? 1 : 0, s);
 
        // Place (0, 0) at the current position.
        ans += IsSumEqualsXor(i + 1, n, 0, s);
    }
 
    // Return the answer
    return dp[i, bound] = ans;
}
 
static String reverse(String input)
{
    char[] a = input.ToCharArray();
    int l, r = a.Length - 1;
     
    for(l = 0; l < r; l++, r--)
    {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.Join("", a);
}
 
// Utility Function to convert N
// to its binary representation
static String convertToBinary(int n)
{
    String ans = "";
    while (n > 0)
    {
        char rem = (char)(n % 2 + '0');
        ans += (rem);
        n /= 2;
    }
    ans = reverse(ans);
    return ans;
}
 
// Function to count pairs (x, y)
// such that x + y = x^y
static void IsSumEqualsXorUtil(int N)
{
     
    // Convert the number to
    // equivalent binary representation
    String s = convertToBinary(N);
 
    // Initialize dp array with -1.
    for(int i = 0; i < dp.GetLength(0); i++)
    {
        for(int j = 0; j < dp.GetLength(1); j++)
        {
            dp[i, j] = -1;
        }
    }
 
    // Print answer returned by recursive function
    Console.Write(IsSumEqualsXor(0, s.Length, 1,
                                 s.ToCharArray()) +"\n");
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Input
    int N = 10;
 
    // Function call
    IsSumEqualsXorUtil(N);
}
}
 
// This code is contributed by umadevi9616

<script>
    // Javascript program for the above approach
     
    // 2D array for memoization
    let dp = new Array(1000);
    for(let i = 0; i < 1000; i++)
    {
        dp[i] = new Array(2);
    }
 
    // Recursive Function to count pairs
    // (x, y) such that x+y = x^y
    function IsSumEqualsXor(i, n, bound, s)
    {
     
        // If the String is traversed completely
        if (i == n)
            return 1;
 
        // If the current subproblem
        // is already calculated
        if (dp[i][bound] != -1)
            return dp[i][bound];
 
        let ans = 0;
 
        // If bound = 1 and  s[i] == '0',
        // only (0, 0) can be placed
        if (bound!=0 && s[i] == '0') {
            ans = IsSumEqualsXor(i + 1, n, 1, s);
        }
 
        // Otherwise
        else {
            // Placing (0, 1) and (1, 0) are
            // equivalent. Hence, multiply by 2.
            ans = 2
                  * IsSumEqualsXor(i + 1, n,
                                   bound!=0 & (s[i] == '1')?1:0, s);
 
            // Place (0, 0) at the current position.
            ans += IsSumEqualsXor(i + 1, n, 0, s);
        }
 
        // Return the answer
        dp[i][bound] = ans
        return dp[i][bound];
    }
    function reverse(input) {
        let a = input.split('');
        let l, r = a.length - 1;
        for (l = 0; l < r; l++, r--) {
            let temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
        return a.join("");
    }
     
    // Utility Function to convert N
    // to its binary representation
    function convertToBinary(n)
    {
        let ans="";
        while (n>0) {
 
            let rem = String.fromCharCode(n % 2 + 48);
            ans+=(rem);
            n = parseInt(n / 2, 10);
        }
        ans = reverse(ans);
        return ans;
    }
 
    // Function to count pairs (x, y)
    // such that x + y = x^y
    function IsSumEqualsXorUtil(N)
    {
        // Convert the number to
        // equivalent binary representation
        let s = convertToBinary(N);
 
        // Initialize dp array with -1.
        for(let i = 0; i < dp.length; i++)
        {
            for (let j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
 
        // Print answer returned by recursive function
        document.write(IsSumEqualsXor(0, s.length, 1, s.split('')) +"</br>");
    }
     
    // Input
    let N = 10;
  
    // Function call
    IsSumEqualsXorUtil(N);
 
// This code is contributed by suresh07.
</script>

37

Complejidad de tiempo: O(Log ₂ N)
Espacio auxiliar: O(Log ₂ N)