Dada una array ordenada arr[] y un entero K , la tarea es verificar si existe un techo del número K dividido por alguna potencia de 2 en la array.
Nota: Si no existe tal elemento, imprima -1.
Ejemplos:
Entrada: arr[] = {3, 5, 7, 8, 10}, K = 4
Salida: -1
Explicación:
No existe tal elemento.
Entrada: arr[] = {1, 2, 3, 5, 7, 8}, K = 4
Salida: 2
Explicación:
Cuando 4 se divide por 2 elevado a 1, existe un elemento en el arreglo.
Enfoque: La idea es probar cada potencia de 2 y comprobar que existe un techo de ese número a partir de la potencia 0. La comprobación de que existe o no un elemento en la array se puede realizar mediante la búsqueda binaria .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 implementation to check
// if a number divided by power
// of two exist in the sorted array
#include <bits/stdc++.h>
using namespace std;
// Function to find there exist a
// number or not in the array
int findNumberDivByPowerofTwo(int ar[],
int k, int n)
{
int found = -1, m = k;
// Loop to check if there exist
// a number by divided by power of 2
while (m > 0)
{
int l = 0;
int r = n - 1;
// Binary Search
while (l <= r)
{
int mid = (l + r) / 2;
if (ar[mid] == m)
{
found = m;
break;
}
else if (ar[mid] > m)
{
r = mid - 1;
}
else if (ar[mid] < m)
{
l = mid + 1;
}
}
// Condition to check the number
// is found in the array or not
if (found != -1)
{
break;
}
// Otherwise divide the number
// by increasing the one more
// power of 2
m = m / 2;
}
return found;
}
// Driver Code
int main()
{
int arr[] = { 3, 5, 7, 8, 10 };
int k = 4, n = 5;
cout << findNumberDivByPowerofTwo(arr, k, n);
}
// This code is contributed by code_hunt
Java
// Java implementation to check
// if a number divided by power
// of two exist in the sorted array
import java.util.Scanner;
public class GreeksForGreeksQuestions {
// Function to find there exist a
// number or not in the array
static int findNumberDivByPowerofTwo(
int[] ar, int k, int n)
{
int found = -1, m = k;
// Loop to check if there exist
// a number by divided by power of 2
while (m > 0) {
int l = 0;
int r = n - 1;
// Binary Search
while (l <= r) {
int mid = (l + r) / 2;
if (ar[mid] == m) {
found = m;
break;
}
else if (ar[mid] > m) {
r = mid - 1;
}
else if (ar[mid] < m) {
l = mid + 1;
}
}
// Condition to check the number
// is found in the array or not
if (found != -1) {
break;
}
// Otherwise divide the number
// by increasing the one more
// power of 2
m = m / 2;
}
return found;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 5, 7, 8, 10 };
int k = 4, n = 5;
System.out.println(
findNumberDivByPowerofTwo(
arr, k, n));
}
}
Python3
# Python3 implementation to check # if a number divided by power # of two exist in the sorted array # Function to find there exist a # number or not in the array def findNumberDivByPowerofTwo(ar, k, n): found = -1 m = k # Loop to check if there exist # a number by divided by power of 2 while (m > 0): l = 0 r = n - 1 # Binary Search while (l <= r): mid = (l + r) // 2 if (ar[mid] == m): found = m break elif (ar[mid] > m): r = mid - 1 elif (ar[mid] < m): l = mid + 1 # Condition to check the number # is found in the array or not if (found != -1): break # Otherwise divide the number # by increasing the one more # power of 2 m = m // 2 return found # Driver Code arr = [ 3, 5, 7, 8, 10 ] k = 4 n = 5 print(findNumberDivByPowerofTwo(arr, k, n)) # This code is contributed by code_hunt
C#
// C# implementation to check
// if a number divided by power
// of two exist in the sorted array
using System;
class GFG{
// Function to find there exist a
// number or not in the array
static int findNumberDivByPowerofTwo(int[] ar, int k,
int n)
{
int found = -1, m = k;
// Loop to check if there exist
// a number by divided by power of 2
while (m > 0)
{
int l = 0;
int r = n - 1;
// Binary Search
while (l <= r)
{
int mid = (l + r) / 2;
if (ar[mid] == m)
{
found = m;
break;
}
else if (ar[mid] > m)
{
r = mid - 1;
}
else if (ar[mid] < m)
{
l = mid + 1;
}
}
// Condition to check the number
// is found in the array or not
if (found != -1)
{
break;
}
// Otherwise divide the number
// by increasing the one more
// power of 2
m = m / 2;
}
return found;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 5, 7, 8, 10 };
int k = 4, n = 5;
Console.WriteLine(findNumberDivByPowerofTwo(
arr, k, n));
}
}
// This code is contributed by princi singh
Javascript
<script>
// javascript implementation to check
// if a number divided by power
// of two exist in the sorted array
// Function to find there exist a
// number or not in the array
function findNumberDivByPowerofTwo(ar , k , n) {
var found = -1, m = k;
// Loop to check if there exist
// a number by divided by power of 2
while (m > 0) {
var l = 0;
var r = n - 1;
// Binary Search
while (l <= r) {
var mid = parseInt((l + r) / 2);
if (ar[mid] == m) {
found = m;
break;
} else if (ar[mid] > m) {
r = mid - 1;
} else if (ar[mid] < m) {
l = mid + 1;
}
}
// Condition to check the number
// is found in the array or not
if (found != -1) {
break;
}
// Otherwise divide the number
// by increasing the one more
// power of 2
m = parseInt(m / 2);
}
return found;
}
// Driver Code
var arr = [ 3, 5, 7, 8, 10 ];
var k = 4, n = 5;
document.write(findNumberDivByPowerofTwo(arr, k, n));
// This code contributed by gauravrajput1
</script>
Producción:
-1
Complejidad de tiempo: O(logn), necesario para realizar operaciones de búsqueda binaria
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional
Publicación traducida automáticamente
Artículo escrito por abhinavpande y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA