Dados dos números x, y que denota el número de bits establecidos. También se da un número C. La tarea es imprimir el número de formas en que podemos formar dos números A y B de modo que A tenga x número de bits establecidos y B tenga y número de bits establecidos y A+B = C.
Ejemplos :
Input: X = 1, Y = 1, C = 3 Output: 2 So two possible ways are (A = 2 and B = 1) and (A = 1 and B = 2) Input: X = 2, Y = 2, C = 20 Output: 3
Enfoque recursivo: el problema anterior se puede resolver usando recursividad . Calcule el recuento total de pares recursivamente. Habrá 4 posibilidades. Comenzamos desde la posición de bit más a la derecha.
- Si la posición del bit en C es 1, entonces hay cuatro posibilidades de obtener 1 en ese índice.
- Si el acarreo es 0, entonces podemos usar 1 bit de X y 0 bit de Y, o viceversa, lo que genera ningún acarreo para el siguiente paso.
- Si el acarreo es 1, entonces podemos usar 1 bit establecido de cada uno, lo que genera un acarreo para el siguiente paso; de lo contrario, no usamos bits establecidos de X e Y, lo que no genera acarreo.
- Si la posición del bit en C es 0, entonces hay cuatro posibilidades de obtener 0 en esa posición del bit.
- Si el acarreo es 1, entonces podemos usar 1 bit establecido de X y 0 bit de Y o viceversa, lo que genera un acarreo de 1 para el siguiente paso.
- Si el acarreo es 0, entonces podemos usar 1 y 1 de X e Y respectivamente, lo que genera un acarreo de 1 para el siguiente paso. También podemos usar bits sin establecer, lo que no genera acarreo para el siguiente paso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Recursive function to generate
// all combinations of bits
int func(int third, int seta, int setb,
int carry, int number)
{
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 and seta == 0 and setb == 0 and carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 or seta < 0 or setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = shift & 1;
int ans = 0;
// carry = 1 and bit set = 1
if ((mask) && carry) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask && !carry) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 0, number)
+ func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (!mask && carry) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 1, number)
+ func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (!mask && !carry) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// Return ans
return ans;
}
// Function to count ways
int possibleSwaps(int a, int b, int c)
{
// Call func
return func(0, a, b, 0, c);
}
// Driver Code
int main()
{
int x = 2, y = 2, c = 20;
cout << possibleSwaps(x, y, c);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
public class GFG{
// Recursive function to generate
// all combinations of bits
static int func(int third, int seta, int setb,
int carry, int number)
{
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 && setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = (shift & 1);
int ans = 0;
// carry = 1 and bit set = 1
if ((mask) == 1 && carry == 1) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 0, number)
+ func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 1, number)
+ func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// Return ans
return ans;
}
// Function to count ways
static int possibleSwaps(int a, int b, int c)
{
// Call func
return func(0, a, b, 0, c);
}
// Driver Code
public static void main(String args[])
{
int x = 2, y = 2, c = 20;
System.out.println(possibleSwaps(x, y, c));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python implementation of above approach # Recursive function to generate # all combinations of bits def func(third, seta, setb, carry, number): # find if C has no more set bits on left shift = (number >> third); # if no set bits are left for C # and there are no set bits for A and B # and the carry is 0, then # this combination is possible if (shift == 0 and seta == 0 and setb == 0 and carry == 0): return 1; # if no set bits are left for C and # requirement of set bits for A and B have exceeded if (shift == 0 or seta < 0 or setb < 0): return 0; # Find if the bit is 1 or 0 at # third index to the left mask = (shift & 1); ans = 0; # carry = 1 and bit set = 1 if ((mask) == 1 and carry == 1): # since carry is 1, and we need 1 at C's bit position # we can use 0 and 0 # or 1 and 1 at A and B bit position ans += func(third + 1, seta, setb, 0, number) + func(third + 1, seta - 1, setb - 1, 1, number); # carry = 0 and bit set = 1 elif(mask == 1 and carry == 0): # since carry is 0, and we need 1 at C's bit position # we can use 1 and 0 # or 0 and 1 at A and B bit position ans += func(third + 1, seta - 1, setb, 0, number) + func(third + 1, seta, setb - 1, 0, number); # carry = 1 and bit set = 0 elif(mask == 0 and carry == 1): # since carry is 1, and we need 0 at C's bit position # we can use 1 and 0 # or 0 and 1 at A and B bit position ans += func(third + 1, seta - 1, setb, 1, number) + func(third + 1, seta, setb - 1, 1, number); # carry = 0 and bit set = 0 elif(mask == 0 and carry == 0): # since carry is 0, and we need 0 at C's bit position # we can use 0 and 0 # or 1 and 1 at A and B bit position ans += func(third + 1, seta, setb, 0, number) + func(third + 1, seta - 1, setb - 1, 1, number); # Return ans return ans; # Function to count ways def possibleSwaps(a, b, c): # Call func return func(0, a, b, 0, c); # Driver Code if __name__ == '__main__': x = 2; y = 2; c = 20; print(possibleSwaps(x, y, c)); # This code is contributed by Rajput-Ji
C#
// C# implementation of above approach
using System;
public class GFG {
// Recursive function to generate
// all combinations of bits
static int func(int third, int seta, int setb,
int carry, int number)
{
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 && setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = (shift & 1);
int ans = 0;
// carry = 1 and bit set = 1
if ((mask) == 1 && carry == 1) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 0, number) +
func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 1, number) +
func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// Return ans
return ans;
}
// Function to count ways
static int possibleSwaps(int a, int b, int c) {
// Call func
return func(0, a, b, 0, c);
}
// Driver Code
public static void Main(String []args) {
int x = 2, y = 2, c = 20;
Console.WriteLine(possibleSwaps(x, y, c));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript implementation of above approach
// Recursive function to generate
// all combinations of bits
function func(third , seta , setb , carry , number) {
// find if C has no more set bits on left
var shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 && setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
var mask = (shift & 1);
var ans = 0;
// carry = 1 and bit set = 1
if ((mask) == 1 && carry == 1) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 0, number) +
func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 1, number) +
func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// Return ans
return ans;
}
// Function to count ways
function possibleSwaps(a , b , c)
{
// Call func
return func(0, a, b, 0, c);
}
// Driver Code
var x = 2, y = 2, c = 20;
document.write(possibleSwaps(x, y, c));
// This code is contributed by Rajput-Ji
</script>
Producción
3
Enfoque eficiente: el problema anterior se puede resolver utilizando la máscara de bits DP .
- Inicialice una array 4-D DP de tamaño 64 * 64 * 64 * 2 ya que 10 ^ 18 tiene un máximo de 64 bits establecidos con -1
- El primer estado de la array DP almacena el número de bits recorridos en C desde la derecha. El segundo estado almacena la cantidad de bits de configuración utilizados de X y el tercer estado almacena la cantidad de bits de configuración utilizados de Y. El cuarto estado es el bit de acarreo que se refiere al acarreo generado cuando realizamos una operación de suma.
- La recurrencia tendrá 4 posibilidades. Comenzamos desde la posición de bit más a la derecha.
- Si la posición del bit en C es 1, entonces hay cuatro posibilidades de obtener 1 en ese índice.
- Si el acarreo es 0, entonces podemos usar 1 bit de X y 0 bit de Y, o viceversa, lo que genera ningún acarreo para el siguiente paso.
- Si el acarreo es 1, entonces podemos usar 1 bit establecido de cada uno, lo que genera un acarreo para el siguiente paso; de lo contrario, no usamos bits establecidos de X e Y, lo que no genera acarreo.
- Si la posición del bit en C es 0, entonces hay cuatro posibilidades de obtener 0 en esa posición del bit.
- Si el acarreo es 1, entonces podemos usar 1 bit establecido de X y 0 bit de Y o viceversa, lo que genera un acarreo de 1 para el siguiente paso.
- Si el acarreo es 0, entonces podemos usar 1 y 1 de X e Y respectivamente, lo que genera un acarreo de 1 para el siguiente paso. También podemos usar bits sin establecer, lo que no genera acarreo para el siguiente paso.
- La suma de todas las posibilidades se almacena en dp[tercero][seta][setb][carry] para evitar volver a visitar los mismos estados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Initial DP array
int dp[64][64][64][2];
// Recursive function to generate
// all combinations of bits
int func(int third, int seta, int setb,
int carry, int number)
{
// if the state has already been visited
if (dp[third][seta][setb][carry] != -1)
return dp[third][seta][setb][carry];
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 and seta == 0 and setb == 0 and carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 or seta < 0 or setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = shift & 1;
dp[third][seta][setb][carry] = 0;
// carry = 1 and bit set = 1
if ((mask) && carry) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask && !carry) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta - 1, setb, 0, number)
+ func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (!mask && carry) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta - 1, setb, 1, number)
+ func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (!mask && !carry) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
return dp[third][seta][setb][carry];
}
// Function to count ways
int possibleSwaps(int a, int b, int c)
{
memset(dp, -1, sizeof(dp));
// function call that returns the
// answer
int ans = func(0, a, b, 0, c);
return ans;
}
// Driver Code
int main()
{
int x = 2, y = 2, c = 20;
cout << possibleSwaps(x, y, c);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GfG {
// Initial DP array
static int dp[][][][] = new int[64][64][64][2];
// Recursive function to generate
// all combinations of bits
static int func(int third, int seta, int setb,
int carry, int number)
{
// if the state has already been visited
if (dp[third][seta][setb][carry] != -1)
return dp[third][seta][setb][carry];
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 && setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = shift & 1;
dp[third][seta][setb][carry] = 0;
// carry = 1 and bit set = 1
if ((mask == 1) && carry == 1) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third][seta][setb][carry]
+= func(third + 1, seta - 1, setb, 0, number)
+ func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third][seta][setb][carry] += func(third + 1, seta - 1, setb, 1, number)
+ func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third][seta][setb][carry] += func(third + 1, seta, setb, 0, number)
+ func(third + 1, seta - 1, setb - 1, 1, number);
}
return dp[third][seta][setb][carry];
}
// Function to count ways
static int possibleSwaps(int a, int b, int c)
{
for(int q = 0; q < 64; q++)
{
for(int r = 0; r < 64; r++)
{
for(int p = 0; p < 64; p++)
{
for(int d = 0; d < 2; d++)
{
dp[q][r][p][d] = -1;
}
}
}
}
// function call that returns the
// answer
int ans = func(0, a, b, 0, c);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int x = 2, y = 2, c = 20;
System.out.println(possibleSwaps(x, y, c));
}
}
Python3
# Python3 implementation of the above approach # Initial DP array dp = [[[[-1, -1] for i in range(64)] for j in range(64)] for k in range(64)] # Recursive function to generate # all combinations of bits def func(third, seta, setb, carry, number): # if the state has already been visited if dp[third][seta][setb][carry] != -1: return dp[third][seta][setb][carry] # find if C has no more set bits on left shift = number >> third # if no set bits are left for C # and there are no set bits for A and B # and the carry is 0, then # this combination is possible if (shift == 0 and seta == 0 and setb == 0 and carry == 0): return 1 # if no set bits are left for C and # requirement of set bits for A and B have exceeded if (shift == 0 or seta < 0 or setb < 0): return 0 # Find if the bit is 1 or 0 at # third index to the left mask = shift & 1 dp[third][seta][setb][carry] = 0 # carry = 1 and bit set = 1 if (mask) and carry: # since carry is 1, and we need 1 at # C's bit position we can use 0 and 0 # or 1 and 1 at A and B bit position dp[third][seta][setb][carry] +=\ func(third + 1, seta, setb, 0, number) + \ func(third + 1, seta - 1, setb - 1, 1, number) # carry = 0 and bit set = 1 elif mask and not carry: # since carry is 0, and we need 1 at C's # bit position we can use 1 and 0 # or 0 and 1 at A and B bit position dp[third][seta][setb][carry] +=\ func(third + 1, seta - 1, setb, 0, number) + \ func(third + 1, seta, setb - 1, 0, number) # carry = 1 and bit set = 0 elif not mask and carry: # since carry is 1, and we need 0 at C's # bit position we can use 1 and 0 # or 0 and 1 at A and B bit position dp[third][seta][setb][carry] +=\ func(third + 1, seta - 1, setb, 1, number) + \ func(third + 1, seta, setb - 1, 1, number) # carry = 0 and bit set = 0 elif not mask and not carry: # since carry is 0, and we need 0 at C's # bit position we can use 0 and 0 # or 1 and 1 at A and B bit position dp[third][seta][setb][carry] += \ func(third + 1, seta, setb, 0, number) + \ func(third + 1, seta - 1, setb - 1, 1, number) return dp[third][seta][setb][carry] # Function to count ways def possibleSwaps(a, b, c): # function call that returns the answer ans = func(0, a, b, 0, c) return ans # Driver Code if __name__ == "__main__": x, y, c = 2, 2, 20 print(possibleSwaps(x, y, c)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
// Initial DP array
static int [,,,]dp = new int[64, 64, 64, 2];
// Recursive function to generate
// all combinations of bits
static int func(int third, int seta, int setb,
int carry, int number)
{
// if the state has already been visited
if (third > -1 && seta > -1 &&
setb > -1 && carry > -1)
if(dp[third, seta, setb, carry] != -1)
return dp[third, seta, setb, carry];
// find if C has no more set bits on left
int shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 &&
setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and
// B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
int mask = shift & 1;
dp[third, seta, setb, carry] = 0;
// carry = 1 and bit set = 1
if ((mask == 1) && carry == 1)
{
// since carry is 1, and we need 1 at
// C's bit position, we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third, seta,
setb, carry] += func(third + 1, seta,
setb, 0, number) +
func(third + 1, seta - 1,
setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0)
{
// since carry is 0, and we need 1 at
// C's bit position, we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third, seta,
setb, carry] += func(third + 1, seta - 1,
setb, 0, number) +
func(third + 1, seta,
setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1)
{
// since carry is 1, and we need 0 at
// C's bit position, we can use 1 and 0
// or 0 and 1 at A and B bit position
dp[third, seta,
setb, carry] += func(third + 1, seta - 1,
setb, 1, number) +
func(third + 1, seta,
setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0)
{
// since carry is 0, and we need 0 at
// C's bit position, we can use 0 and 0
// or 1 and 1 at A and B bit position
dp[third, seta,
setb, carry] += func(third + 1, seta,
setb, 0, number) +
func(third + 1, seta - 1,
setb - 1, 1, number);
}
return dp[third, seta, setb, carry];
}
// Function to count ways
static int possibleSwaps(int a, int b, int c)
{
for(int q = 0; q < 64; q++)
{
for(int r = 0; r < 64; r++)
{
for(int p = 0; p < 64; p++)
{
for(int d = 0; d < 2; d++)
{
dp[q, r, p, d] = -1;
}
}
}
}
// function call that returns the
// answer
int ans = func(0, a, b, 0, c);
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int x = 2, y = 2, c = 20;
Console.WriteLine(possibleSwaps(x, y, c));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of above approach
// Recursive function to generate
// all combinations of bits
function func(third , seta , setb , carry , number) {
// find if C has no more set bits on left
var shift = (number >> third);
// if no set bits are left for C
// and there are no set bits for A and B
// and the carry is 0, then
// this combination is possible
if (shift == 0 && seta == 0 && setb == 0 && carry == 0)
return 1;
// if no set bits are left for C and
// requirement of set bits for A and B have exceeded
if (shift == 0 || seta < 0 || setb < 0)
return 0;
// Find if the bit is 1 or 0 at
// third index to the left
var mask = (shift & 1);
var ans = 0;
// carry = 1 and bit set = 1
if ((mask) == 1 && carry == 1) {
// since carry is 1, and we need 1 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// carry = 0 and bit set = 1
else if (mask == 1 && carry == 0) {
// since carry is 0, and we need 1 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 0, number) +
func(third + 1, seta, setb - 1, 0, number);
}
// carry = 1 and bit set = 0
else if (mask == 0 && carry == 1) {
// since carry is 1, and we need 0 at C's bit position
// we can use 1 and 0
// or 0 and 1 at A and B bit position
ans += func(third + 1, seta - 1, setb, 1, number) +
func(third + 1, seta, setb - 1, 1, number);
}
// carry = 0 and bit set = 0
else if (mask == 0 && carry == 0) {
// since carry is 0, and we need 0 at C's bit position
// we can use 0 and 0
// or 1 and 1 at A and B bit position
ans += func(third + 1, seta, setb, 0, number) +
func(third + 1, seta - 1, setb - 1, 1, number);
}
// Return ans
return ans;
}
// Function to count ways
function possibleSwaps(a , b , c)
{
// Call func
return func(0, a, b, 0, c);
}
// Driver Code
var x = 2, y = 2, c = 20;
document.write(possibleSwaps(x, y, c));
// This code contributed by Rajput-Ji
</script>
Producción:
3