Dada una array A de N enteros, donde:
- Cada elemento de la array representa el tamaño de bits de un tipo de datos entero sin signo imaginario.
- Si un tipo de datos imaginario tiene un tamaño de A[i] bits , entonces puede almacenar números enteros de tamaño 0 a 2 A[i] -1.
La tarea es verificar si existe algún número entero X , tal que:
- X está en el rango de 1 a N
- X puede caber en un tipo de datos de tamaño de bit A[i]
- X 2 no encaja en ningún otro tipo de datos distinto de tamaño de bit A[j] (A[i] < A[j]), ni siquiera con ceros a la izquierda.
Ejemplos:
Entrada: N = 4, A = {4, 2, 3, 1}
Salida: SÍ
Explicación: Sea X = 7. Ahora, 7 = (111) 2.
Claramente, 7 cabe en 3 bits (3 está presente en el arreglo dado ).
7 2 = 49 , que es igual a (110001) 2 , que claramente no cabe en 4 bits .Entrada: N = 3 , A = {16, 64, 32}
Salida: NO
Enfoque: La idea es verificar si hay un par (a, b) en la array, de modo que para el par exista un número entero X que quepa en a bits y X*X no quepa en b bits.
Observaciones:
El mejor candidato para X es el mayor número posible que cabe en un bit. (es decir, 2 a -1). La razón es que aumenta la posibilidad de existencia de tal b , de modo que X*X no cabe en b bits.
Si un entero X = 2 a – 1 , entonces X * X = (2 a – 1) * (2 a – 1) , lo que requeriría almacenar 2*a bits.
Entonces, para cada elemento A[i], sería suficiente verificar si el elemento más pequeño mayor que él es menor que 2 * A[i] o no.
Con base en la observación anterior, se puede utilizar el siguiente enfoque para resolver el problema:
- Ordenar la array dada.
- Itere a través de la array y verifique si algún elemento es menos del doble de su elemento anterior.
- Si es así, devuelve verdadero.
- Si la iteración se completa sin devolver verdadero, devuelve falso.
El siguiente es el código basado en el enfoque anterior:
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there exist
// an integer X, such that X fits in bits
// represented by some array element and
// X*X does not fit in bits represented
// by some other element
bool check(int N, int A[])
{
// sorting the given array
sort(A, A + N);
// iterating through the array
for (int i = 1; i < N; i++) {
// If an element is equal to the
// last element simply skip that
// case and continue the iteration
// as the task is to find two
// distinct integers such that
// X fits in one them and
// X*X does not fit in other
if (A[i] == A[i - 1]) {
continue;
}
// If the value of an element is
// less than twice of its
// previous element, that means
// X would fit in previous element bits,
// but X*X would not fit in current
// element bits
if (A[i] < 2 * A[i - 1]) {
return true;
}
}
// return false if iterations completes
return false;
}
// Driver Code
int main()
{
int N = 4;
int A[] = { 4, 2, 3, 1 };
bool answer = check(N, A);
if (answer == true) {
cout << "YES";
}
else {
cout << "NO";
}
}
Java
// JAVA code for above approach
import java.util.*;
class GFG
{
// Function to check if there exist
// an integer X, such that X fits in bits
// represented by some array element and
// X*X does not fit in bits represented
// by some other element
public static boolean check(int N, int A[])
{
// sorting the given array
Arrays.sort(A);
// iterating through the array
for (int i = 1; i < N; i++) {
// If an element is equal to the
// last element simply skip that
// case and continue the iteration
// as the task is to find two
// distinct integers such that
// X fits in one them and
// X*X does not fit in other
if (A[i] == A[i - 1]) {
continue;
}
// If the value of an element is
// less than twice of its
// previous element, that means
// X would fit in previous element bits,
// but X*X would not fit in current
// element bits
if (A[i] < 2 * A[i - 1]) {
return true;
}
}
// return false if iterations completes
return false;
}
// Driver Code
public static void main(String args[])
{
int N = 4;
int A[] = new int[] { 4, 2, 3, 1 };
boolean answer = check(N, A);
if (answer == true) {
System.out.print("YES");
}
else {
System.out.print("NO");
}
}
}
// This code is contributed by Taranpreet
Python3
# Python code for above approach
# Function to check if there exist
# an integer X, such that X fits in bits
# represented by some array element and
# X*X does not fit in bits represented
# by some other element
def check(N, A):
# sorting the given array
A.sort()
# iterating through the array
for i in range(1,N):
# If an element is equal to the
# last element simply skip that
# case and continue the iteration
# as the task is to find two
# distinct integers such that
# X fits in one them and
# X*X does not fit in other
if (A[i] == A[i - 1]):
continue
# If the value of an element is
# less than twice of its
# previous element, that means
# X would fit in previous element bits,
# but X*X would not fit in current
# element bits
if (A[i] < 2 * A[i - 1]):
return True
# return false if iterations completes
return False
# Driver Code
N = 4
A = [ 4, 2, 3, 1 ]
answer = check(N, A)
if (answer == True):
print("YES")
else:
print("NO")
# This code is contributed by shinjanpatra
C#
// C# code for above approach
using System;
public class GFG{
// Function to check if there exist
// an integer X, such that X fits in bits
// represented by some array element and
// X*X does not fit in bits represented
// by some other element
static bool check(int N, int[] A)
{
// sorting the given array
Array.Sort(A);
// iterating through the array
for (int i = 1; i < N; i++) {
// If an element is equal to the
// last element simply skip that
// case and continue the iteration
// as the task is to find two
// distinct integers such that
// X fits in one them and
// X*X does not fit in other
if (A[i] == A[i - 1]) {
continue;
}
// If the value of an element is
// less than twice of its
// previous element, that means
// X would fit in previous element bits,
// but X*X would not fit in current
// element bits
if (A[i] < 2 * A[i - 1]) {
return true;
}
}
// return false if iterations completes
return false;
}
// Driver Code
static public void Main (){
int N = 4;
int[] A = { 4, 2, 3, 1 };
bool answer = check(N, A);
if (answer == true) {
Console.Write("YES");
}
else {
Console.Write("NO");
}
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
// Function to check if there exist
// an integer X, such that X fits in bits
// represented by some array element and
// X*X does not fit in bits represented
// by some other element
function check(N, A) {
// sorting the given array
A.sort();
// iterating through the array
for (let i = 1; i < N; i++) {
// If an element is equal to the
// last element simply skip that
// case and continue the iteration
// as the task is to find two
// distinct integers such that
// X fits in one them and
// X*X does not fit in other
if (A[i] == A[i - 1]) {
continue;
}
// If the value of an element is
// less than twice of its
// previous element, that means
// X would fit in previous element bits,
// but X*X would not fit in current
// element bits
if (A[i] < 2 * A[i - 1]) {
return true;
}
}
// return false if iterations completes
return false;
}
// Driver Code
let N = 4;
let A = [4, 2, 3, 1];
let answer = check(N, A);
if (answer == true) {
document.write("YES");
}
else {
document.write("NO");
}
// This code is contributed by Potta Lokesh
</script>
Producción
YES
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA