Dados dos números enteros N y M , la tarea es imprimir todos los elementos en el rango [N, M] que tengan al menos un divisor impar.
Ejemplos:
Entrada: N = 2, M = 10
Salida: 3 5 6 7 9 10
Explicación:
3, 6 tienen un divisor impar 3
5, 10 tienen un divisor impar 5
7 tienen un divisor impar 7
9 tienen dos divisores impares 3, 9
Entrada : N = 15, M = 20
Salida: 15 17 18 19 20
Enfoque ingenuo:
el enfoque más simple es recorrer todos los números en el rango [1, N] y, para cada elemento, verificar si tiene un divisor impar o no.
Complejidad de tiempo: O(N 3/2 )
Enfoque eficiente:
Para optimizar el enfoque anterior, debemos observar los siguientes detalles:
- Cualquier número que sea potencia de 2 no tiene divisores impares.
- Todos los demás elementos tendrán al menos un divisor impar
Ilustración:
En el rango [3, 10], los elementos que tienen al menos un divisor impar son {3, 5, 6, 7, 9, 10} y {4, 8} no contiene ningún divisor impar.
Siga los pasos a continuación para resolver el problema:
- Recorra el rango [N, M] y verifique para cada elemento si alguno de sus bits establecidos está establecido en el número anterior o no, es decir, verifique si i & (i – 1) es igual a 0 o no.
- Si es así, entonces el número es una potencia de 2 y no se considera. De lo contrario, imprima el número ya que no es una potencia de 2 y tiene al menos un divisor impar.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print all numbers // with least one odd factor in the // given range #include <bits/stdc++.h> using namespace std; // Function to prints all numbers // with at least one odd divisor int printOddFactorNumber(int n, int m) { for (int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) cout << i << " "; } } // Driver Code int main() { int N = 2, M = 10; printOddFactorNumber(N, M); return 0; }
Java
// Java program to print all numbers // with least one odd factor in the // given range class GFG{ // Function to prints all numbers // with at least one odd divisor static int printOddFactorNumber(int n, int m) { for (int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) System.out.print(i + " "); } return 0; } // Driver Code public static void main(String[] args) { int N = 2, M = 10; printOddFactorNumber(N, M); } } // This code is contributed // by shivanisinghss2110
Python3
# Python3 program to print all numbers # with least one odd factor in the # given range # Function to prints all numbers # with at least one odd divisor def printOddFactorNumber(n, m): for i in range(n, m + 1): # Check if the number is # not a power of two if ((i > 0) and ((i & (i - 1)) != 0)): print(i, end = " ") # Driver Code N = 2 M = 10 printOddFactorNumber(N, M) # This code is contributed by Vishal Maurya
C#
// C# program to print all numbers // with least one odd factor in the // given range using System; class GFG{ // Function to prints all numbers // with at least one odd divisor static int printOddFactorNumber(int n, int m) { for (int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) Console.Write(i + " "); } return 0; } // Driver Code public static void Main() { int N = 2, M = 10; printOddFactorNumber(N, M); } } // This code is contributed // by Code_Mech
Javascript
<script> // JavaScript program to implement // the above approach // Function to prints all numbers // with at least one odd divisor function printOddFactorNumber(n, m) { for (let i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) document.write(i + " "); } return 0; } // Driver code let N = 2, M = 10; printOddFactorNumber(N, M); // This code is contributed by susmitakundugoaldanga. </script>
3 5 6 7 9 10
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Ganeshchowdharysadanala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA