Dado un entero ‘x’, encuentra el número de valores de ‘a’ que satisfacen las siguientes condiciones:
- 0 <= un <= x
- a XOR x = a + x
Ejemplos:
Input : 5 Output : 2 Explanation: For x = 5, following 2 values of 'a' satisfy the conditions: 5 XOR 0 = 5+0 5 XOR 2 = 5+2 Input : 10 Output : 4 Explanation: For x = 10, following 4 values of 'a' satisfy the conditions: 10 XOR 0 = 10+0 10 XOR 1 = 10+1 10 XOR 4 = 10+4 10 XOR 5 = 10+5
Enfoque ingenuo:
un enfoque simple es verificar todos los valores de ‘a’ entre 0 y ‘x’ (ambos inclusive) y calcular su XOR con x y verificar si se cumple la condición 2.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find count of values whose XOR
// with x is equal to the sum of value and x
// and values are smaller than equal to x
#include <bits/stdc++.h>
using namespace std;
int FindValues(int x)
{
// Initialize result
int count = 0;
// Traversing through all values between
// 0 and x both inclusive and counting
// numbers that satisfy given property
for (int i = 0; i <= x; i++)
if ((x + i) == (x ^ i))
count++;
return count;
}
// Driver code
int main()
{
int x = 10;
// Function call
cout << FindValues(x);
return 0;
}
Java
// Java program to find count of values whose XOR
// with x is equal to the sum of value and x
// and values are smaller than equal to x
class Fib
{
static int FindValues(int x)
{
// Initialize result
int count = 0;
// Traversing through all values between
// 0 and x both inclusive and counting
// numbers that satisfy given property
for (int i = 0; i <= x; i++)
if ((x + i) == (x ^ i))
count++;
return count;
}
// Driver code
public static void main(String[] args)
{
int x = 10;
// Function call
System.out.println(FindValues(x));
}
}
Python3
# Python3 program to find count of # values whose XOR with x is equal # to the sum of value and x and # values are smaller than equal to x def FindValues(x): # Initialize result count = 0 # Traversing through all values # between 0 and x both inclusive # and counting numbers that # satisfy given property for i in range(0, x): if ((x + i) == (x ^ i)): count = count + 1 return count # Driver code x = 10 # Function call print(FindValues(x)) # This code is contributed # by Shivi_Aggarwal
C#
// C# program to find count of values whose XOR
// with x is equal to the sum of value and x
// and values are smaller than equal to x
using System;
class Fib
{
static int FindValues(int x)
{
// Initialize result
int count = 0;
// Traversing through all values between
// 0 and x both inclusive and counting
// numbers that satisfy given property
for (int i = 0; i <= x; i++)
if ((x + i) == (x ^ i))
count++;
return count;
}
// Driver code
public static void Main()
{
int x = 10;
// Function call
Console.Write(FindValues(x));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find count
// of values whose XOR with x
// is equal to the sum of value
// and x and values are smaller
// than equal to x
// function return the
// value of count
function FindValues($x)
{
// Initialize result
$count = 0;
// Traversing through all values between
// 0 and x both inclusive and counting
// numbers that satisfy given property
for ($i = 0; $i <= $x; $i++)
if (($x + $i) == ($x ^ $i))
$count++;
return $count;
}
// Driver code
$x = 10;
// Function call
echo FindValues($x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find count of values whose XOR
// with x is equal to the sum of value and x
// and values are smaller than equal to x
function FindValues(x)
{
// Initialize result
let count = 0;
// Traversing through all values between
// 0 and x both inclusive and counting
// numbers that satisfy given property
for (let i = 0; i <= x; i++)
if ((x + i) == (x ^ i))
count++;
return count;
}
let x = 10;
// Function call
document.write(FindValues(x));
</script>
Producción
4
Complejidad temporal: O(x).
Espacio Auxiliar: O(1)
Enfoque eficiente:
XOR simula la suma binaria sin el traslado al siguiente dígito. Para los dígitos cero de ‘a’ podemos agregar un 1 o un 0 sin obtener un acarreo, lo que implica xor = + mientras que si un dígito en ‘a’ es 1, entonces el dígito coincidente en x debe ser 0 para evitar llevar. Para cada 0 en ‘a’ en el dígito coincidente en x puede ser un 1 o un 0 con una combinación total de 2^(número de cero). Por lo tanto, solo necesitamos contar el número de 0 en la representación binaria del número y la respuesta será 2^ (número de ceros).
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count numbers whose bitwise
// XOR and sum with x are equal
#include <bits/stdc++.h>
using namespace std;
// Function to find total 0 bit in a number
long CountZeroBit(long x)
{
unsigned int count = 0;
while (x)
{
if (!(x & 1LL))
count++;
x >>= 1LL;
}
return count;
}
// Function to find Count of non-negative numbers
// less than or equal to x, whose bitwise XOR and
// SUM with x are equal.
long CountXORandSumEqual(long x)
{
// count number of zero bit in x
long count = CountZeroBit(x);
// power of 2 to count
return (1LL << count);
}
// Driver code
int main()
{
long x = 10;
// Function call
cout << CountXORandSumEqual(x);
return 0;
}
Java
// Java program to count
// numbers whose bitwise
// XOR and sum with x
// are equal
import java.io.*;
class GFG {
// Function to find total
// 0 bit in a number
static long CountZeroBit(long x)
{
long count = 0;
while (x > 0) {
if ((x & 1L) == 0)
count++;
x >>= 1L;
}
return count;
}
// Function to find Count
// of non-negative numbers
// less than or equal to x,
// whose bitwise XOR and
// SUM with x are equal.
static long CountXORandSumEqual(long x)
{
// count number of
// zero bit in x
long count = CountZeroBit(x);
// power of 2 to count
return (1L << count);
}
// Driver code
public static void main(String[] args)
{
long x = 10;
// Function call
System.out.println(CountXORandSumEqual(x));
}
}
// The code is contributed by ajit
Python3
# Python3 program to count numbers whose bitwise # XOR and sum with x are equal # Function to find total 0 bit in a number def CountZeroBit(x): count = 0 while (x): if ((x & 1) == 0): count += 1 x >>= 1 return count # Function to find Count of non-negative numbers # less than or equal to x, whose bitwise XOR and # SUM with x are equal. def CountXORandSumEqual(x): # count number of zero bit in x count = CountZeroBit(x) # power of 2 to count return (1 << count) # Driver code if __name__ == '__main__': x = 10 # Function call print(CountXORandSumEqual(x)) # This code is contributed by 29AjayKumar
C#
// C# program to count
// numbers whose bitwise
// XOR and sum with x
// are equal
using System;
class GFG {
// Function to find total
// 0 bit in a number
static int CountZeroBit(int x)
{
int count = 0;
while (x > 0) {
if ((x & 1) == 0)
count++;
x >>= 1;
}
return count;
}
// Function to find Count
// of non-negative numbers
// less than or equal to x,
// whose bitwise XOR and
// SUM with x are equal.
static int CountXORandSumEqual(int x)
{
// count number of
// zero bit in x
int count = CountZeroBit(x);
// power of 2 to count
return (1 << count);
}
// Driver code
static public void Main()
{
int x = 10;
// Function call
Console.WriteLine(CountXORandSumEqual(x));
}
}
// The code is contributed by ajit
PHP
<?php
// PHP program to count numbers whose bitwise
// XOR and sum with x are equal
// Function to find total 0 bit in a number
function CountZeroBit($x)
{
$count = 0;
while ($x)
{
if (!($x & 1))
$count++;
$x >>= 1;
}
return $count;
}
// Function to find Count of
// non-negative numbers less
// than or equal to x, whose
// bitwise XOR and SUM with
// x are equal.
function CountXORandSumEqual($x)
{
// count number of zero bit in x
$count = CountZeroBit($x);
// power of 2 to count
return (1 << $count);
}
// Driver code
$x = 10;
// Function call
echo CountXORandSumEqual($x);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to count
// numbers whose bitwise
// XOR and sum with x
// are equal
// Function to find total
// 0 bit in a number
function CountZeroBit(x)
{
let count = 0;
while (x > 0)
{
if ((x & 1) == 0)
count++;
x >>= 1;
}
return count;
}
// Function to find Count
// of non-negative numbers
// less than or equal to x,
// whose bitwise XOR and
// SUM with x are equal.
function CountXORandSumEqual(x)
{
// count number of
// zero bit in x
let count = CountZeroBit(x);
// power of 2 to count
return (1 << count);
}
// Driver code
let x = 10;
// Function call
document.write(CountXORandSumEqual(x));
// This code is contributed by suresh07
</script>
Producción
4
Complejidad del tiempo: O(Log x)
Espacio Auxiliar: O(1)
Este artículo es una contribución de DANISH KALEEM . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA