Dada una array arr[] que consta de N enteros, la tarea es contar el número de enteros en el rango [1, arr[i]] que no contiene ningún divisor impar .
Ejemplos:
Entrada: arr[] = {15, 16, 20, 35}
Salida: 3 4 4 5
Explicación:
Los números sin divisores impares de 1 a arr[0] ( = 15) , son 2, 4, 8. Por lo tanto, el cuenta es 3.
De manera similar, para arr[1] (= 16), arr[2] (= 20), arr[3] (= 35) la cuenta es 4, 4 y 5 respectivamente.Entrada: arr[] = {24}
Salida: 4
Enfoque ingenuo: el enfoque más simple es recorrer la array y, para cada elemento de la array arr[i] , verificar si un número tiene divisores impares en el rango [1, arr[i]] o no. Si no tiene divisores impares, incrementa la cuenta. De lo contrario, continúe con el siguiente número entero. Finalmente, imprima el conteo obtenido para cada elemento del arreglo arr[i] .
Complejidad de tiempo: O(N*max(arr[i]))
Espacio auxiliar: O(1)
Enfoque eficiente: la idea óptima se basa en la siguiente observación:
Observación:
Cualquier número se puede representar de la forma p 1 x 1 * p 2 x 2 *- – -*p N x N , donde p i es un número primo y x i es su potencia. Si el número no tiene ningún divisor impar, entonces no debe contener ningún factor primo impar .
Por lo tanto, el problema se reduce a encontrar el conteo de números enteros en el rango de 1 a N tal que esos números sean una potencia de dos , lo que se puede hacer en complejidad de tiempo log(N) comprobando repetidamente la potencia de dos tal que 2 i ≤ N y conteo creciente en cada paso.
Siga los pasos a continuación para resolver el problema:
- Recorra la array arr[] y realice las siguientes operaciones:
- Inicialice dos variables, digamos powerOfTwo , para verificar la potencia máxima de 2 que es menor que arr[i] y otra variable, digamos count , para almacenar el conteo de enteros en el rango [1, arr[i]] sin divisores impares .
- Encuentre para cada elemento de la array, el valor de powerOfTwo y count .
- Imprímalos como la respuesta para cada elemento de la array.
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 integers in the
// range 1 to N having no odd divisors
void oddDivisors(int arr[], int N)
{
// Traverse the array
for (int i = 0; i < N; i++) {
// Stores the nearest power
// of two less than arr[i]
int powerOfTwo = 2;
// Stores the count of integers
// with no odd divisor for each query
int count = 0;
// Iterate until powerOfTwo is
// less then or equal to arr[i]
while (powerOfTwo <= arr[i]) {
count++;
powerOfTwo = 2 * powerOfTwo;
}
// Print the answer for
// the current element
cout << count << " ";
}
return;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 15, 16, 20, 35 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
oddDivisors(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count integers in the
// range 1 to N having no odd divisors
static void oddDivisors(int arr[], int N)
{
// Traverse the array
for (int i = 0; i < N; i++)
{
// Stores the nearest power
// of two less than arr[i]
int powerOfTwo = 2;
// Stores the count of integers
// with no odd divisor for each query
int count = 0;
// Iterate until powerOfTwo is
// less then or equal to arr[i]
while (powerOfTwo <= arr[i])
{
count++;
powerOfTwo = 2 * powerOfTwo;
}
// Print the answer for
// the current element
System.out.print(count + " ");
}
return;
}
// Driver Code
public static void main(String args[])
{
// Given array
int arr[] = { 15, 16, 20, 35 };
// Size of the array
int N = arr.length;
oddDivisors(arr, N);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach # Function to count integers in the # range 1 to N having no odd divisors def oddDivisors(arr, N) : # Traverse the array for i in range(N) : # Stores the nearest power # of two less than arr[i] powerOfTwo = 2; # Stores the count of integers # with no odd divisor for each query count = 0; # Iterate until powerOfTwo is # less then or equal to arr[i] while (powerOfTwo <= arr[i]) : count += 1; powerOfTwo = 2 * powerOfTwo; # Print the answer for # the current element print(count, end = " "); # Driver Code if __name__ == "__main__" : # Given array arr = [ 15, 16, 20, 35 ]; # Size of the array N = len(arr); oddDivisors(arr, N); # This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to count integers in the
// range 1 to N having no odd divisors
static void oddDivisors(int[] arr, int N)
{
// Traverse the array
for (int i = 0; i < N; i++)
{
// Stores the nearest power
// of two less than arr[i]
int powerOfTwo = 2;
// Stores the count of integers
// with no odd divisor for each query
int count = 0;
// Iterate until powerOfTwo is
// less then or equal to arr[i]
while (powerOfTwo <= arr[i])
{
count++;
powerOfTwo = 2 * powerOfTwo;
}
// Print the answer for
// the current element
Console.Write(count + " ");
}
return;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] arr = { 15, 16, 20, 35 };
// Size of the array
int N = arr.Length;
oddDivisors(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count integers in the
// range 1 to N having no odd divisors
function oddDivisors(arr , N) {
// Traverse the array
for (i = 0; i < N; i++) {
// Stores the nearest power
// of two less than arr[i]
var powerOfTwo = 2;
// Stores the count of integers
// with no odd divisor for each query
var count = 0;
// Iterate until powerOfTwo is
// less then or equal to arr[i]
while (powerOfTwo <= arr[i]) {
count++;
powerOfTwo = 2 * powerOfTwo;
}
// Print the answer for
// the current element
document.write(count + " ");
}
return;
}
// Driver Code
// Given array
var arr = [ 15, 16, 20, 35 ];
// Size of the array
var N = arr.length;
oddDivisors(arr, N);
// This code contributed by aashish1995
</script>
3 4 4 5
Complejidad de tiempo: O(N * log(max(arr[i]))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA