Dado un número entero N , la tarea es imprimir el recuento de todos los números enteros no negativos K menores o iguales a N, de modo que el XOR bit a bit de K y K+1 sea igual al XOR bit a bit de K+2 y K+3 .
Ejemplos:
Entrada: N = 3
Salida: 2
Explicación:
Los números que cumplen las condiciones son:
- K = 0, el XOR bit a bit de 0 y 1 es igual a 1 y el xor bit a bit de 2 y 3 también es igual a 1.
- K = 2, el XOR bit a bit de 2 y 3 es igual a 1 y el xor bit a bit de 4 y 5 también es igual a 1.
Por lo tanto, hay 2 números que cumplen la condición.
Entrada: 4
Salida: 3
Enfoque ingenuo: el enfoque más simple es iterar sobre el rango [0, N] y verificar si el número actual cumple la condición o no. Si satisface, incremente el conteo en 1 . Después de verificar todos los números, imprima el valor del conteo.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior puede optimizarse mediante la observación de que todos los números pares en el rango [0, N] satisfacen la condición dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count all the integers // less than N satisfying the given // condition int countXor(int N) { // Store the count of even // numbers less than N+1 int cnt = N / 2 + 1; // Return the count return cnt; } // Driver Code int main() { // Given Input int N = 4; // Function Call cout << countXor(N); return 0; }
Java
// Java Program for the above approach import java.io.*; class GFG { // Function to count all the integers // less than N satisfying the given // condition static int countXor(int N) { // Store the count of even // numbers less than N+1 int cnt = (int) N / 2 + 1; // Return the count return cnt; } // Driver Code public static void main(String[] args) { // Given Input int N = 4; // Function Call System.out.println(countXor(N)); } } // This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to count all the integers # less than N satisfying the given # condition def countXor(N): # Store the count of even # numbers less than N+1 cnt = N // 2 + 1 # Return the count return cnt # Driver Code if __name__ == '__main__': # Given Input N = 4 # Function Call print(countXor(N)) # This code is contributed by SUTENDRA_GANGWAR.
C#
// C# program for the above approach using System; class GFG{ // Function to count all the integers // less than N satisfying the given // condition static int countXor(int N) { // Store the count of even // numbers less than N+1 int cnt = (int)N / 2 + 1; // Return the count return cnt; } // Driver code static void Main() { // Given Input int N = 4; // Function Call Console.WriteLine(countXor(N)); } } // This code is contributed by abhinavjain194
Javascript
<script> // JavaScript program for the above approach // Function to count all the integers // less than N satisfying the given // condition function countXor(N) { // Store the count of even // numbers less than N+1 let cnt = Math.floor(N / 2) + 1; // Return the count return cnt; } // Driver Code // Given Input let N = 4; // Function Call document.write(countXor(N)); // This code is contributed by Potta Lokesh </script>
3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA