Compruebe si una array arr[] se puede reorganizar de manera que arr[2 × i + 1] = 2* arr[2 × i] para cada i-ésimo índice

Dada una array arr[] que consta de 2*N enteros, la tarea es verificar si es posible reorganizar los elementos de la array de manera que arr[2 * i + 1] = 2* arr[2 * i] para cada i ^-ésimo índice. Si es posible hacerlo, imprima “Sí . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {4, -2, 2, -4}, N = 2
Salida: Sí
Explicación: Reorganice la array como arr[] = {-2, -4, 2, 4}.

Entrada: arr[] = {3, 1, 3, 6}, N = 2
Salida: No

Enfoque: La idea para resolver el problema dado es usar un Mapa y la observación de que se necesitan N pares distintos de modo que un elemento sea el doble que otro elemento. Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa < integer, integer > , digamos, count , para almacenar el conteo de elementos de la array.
• Recorra la array arr[] y actualice el conteo de cada elemento en Map count .
• Iterar sobre el conteo de mapas y realizar las siguientes operaciones:
  • Inicialice una variable, digamos want , para formar un par con el elemento actual, digamos X , y asigne want = X/2 , si X es menor que 0 . De lo contrario, asigne querer = 2*X.
  • Verifique si X es menor que 0 y X es impar o si el conteo de X es mayor que el conteo de querer , luego imprima «No» ya que es imposible formar el par de X restantes con cualquier otro elemento de la array.
  • De lo contrario, actualice el conteo de deseos en el conteo del mapa como conteo (deseo) – conteo (X).
• Después de completar los pasos anteriores, imprima «Sí» , ya que existe cualquier combinación de elementos que satisfagan la propiedad dada.

A continuación se muestra la implementación del enfoque anterior:

// cpp program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to rearrange the array elements
// that satisfies the given conditions
string canReorderDoubled(vector<int> A)
{
   
    // Stores the count of elements
    map<int,int> count;
 
    // Update the hash table
    for (int a : A)
        count[a]++;
 
    // Traverse the hash table
    for (auto x : count) {
 
        // If the count of current
        // element is zero
        if (x.second == 0)
            continue;
 
        // Stores the element needed
        // to form a pair with the
        // current element
        int xx = x.first;
        int want = xx < 0 ? xx / 2 : xx * 2;
 
        // If x is less than zero and odd
        if (xx < 0 && xx % 2 != 0)
            return "No";
 
        // If count of x is greater
        // than count of want
        if (x.second
            > count[want])
            return "No";
 
        // Update the count of want
        // in the hash table
        count[want] -= x.second;
    }
 
    // Return true if none of the
    // above cases satisfies
    return "Yes";
}
 
// Driver Code
int main()
{
 
    vector<int> arr = { 4, -2, 2, -4 };
    int N = 2;
 
    string res = canReorderDoubled(arr);
 
    // Print the result obtained
    cout<<(res);
}
 
// This code is contributed by mohit kumar 29.

// Java program of the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to check if it is possible
    // to rearrange the array elements
    // that satisfies the given conditions
    public static String canReorderDoubled(int[] A)
    {
        // Stores the count of elements
        Map<Integer, Integer> count
            = new TreeMap<>();
 
        // Update the hash table
        for (int a : A)
            count.put(
                a, count.getOrDefault(a, 0) + 1);
 
        // Traverse the hash table
        for (int x : count.keySet()) {
 
            // If the count of current
            // element is zero
            if (count.get(x) == 0)
                continue;
 
            // Stores the element needed
            // to form a pair with the
            // current element
            int want = x < 0 ? x / 2 : x * 2;
 
            // If x is less than zero and odd
            if (x < 0 && x % 2 != 0)
                return "No";
 
            // If count of x is greater
            // than count of want
            if (count.get(x)
                > count.getOrDefault(want, 0))
                return "No";
 
            // Update the count of want
            // in the hash table
            count.put(want,
                      count.get(want)
                          - count.get(x));
        }
 
        // Return true if none of the
        // above cases satisfies
        return "Yes";
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int[] arr = { 4, -2, 2, -4 };
        int N = 2;
 
        String res = canReorderDoubled(arr);
 
        // Print the result obtained
        System.out.println(res);
    }
}

# Python 3 program of the above approach
 
# Function to check if it is possible
# to rearrange the array elements
# that satisfies the given conditions
 
def canReorderDoubled(A):
    # Stores the count of elements
    count = {}
 
    # Update the hash table
    for a in A:
        if a in count:
            count[a] += 1
        else:
            count[a] = 1
 
    # Traverse the hash table
    for key,value in count.items():
        # If the count of current
        # element is zero
        if (value == 0):
            continue
 
        # Stores the element needed
        # to form a pair with the
        # current element
        xx = key
        if xx < 0:
            want = xx / 2
        else:
            want = xx * 2
 
        # If x is less than zero and odd
        if (xx < 0 and xx % 2 != 0):
            return "No"
 
        # If count of x is greater
        # than count of want
        if (want in count and value > count[want]):
            return "No"
 
        # Update the count of want
        # in the hash table
        if want in count:
          count[want] -= value
 
    # Return true if none of the
    # above cases satisfies
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    arr =  [4, -2, 2, -4]
    N = 2
 
    res = canReorderDoubled(arr)
 
    # Print the result obtained
    print(res)
 
    # This code is contributed by bgangwar59.

<script>
 
// Javascript program of the above approach
 
// Function to check if it is possible
// to rearrange the array elements
// that satisfies the given conditions
function canReorderDoubled(A)
{
   
    // Stores the count of elements
    var count= new Map();
 
    // Update the hash table
    A.forEach(a => {
        if(count.has(a))
            count.set(a, count.get(a)+1)
        else
            count.set(a, 1)
    });
 
    // Traverse the hash table
    count.forEach((value, key) => {
         
 
        // If the count of current
        // element is zero
        if (value != 0)
        {
 
            // Stores the element needed
            // to form a pair with the
            // current element
            var xx = key;
                var want = xx < 0 ? xx / 2 : xx * 2;
 
            // If x is less than zero and odd
            if (xx < 0 && xx % 2 != 0)
                    return "No";
 
            // If count of x is greater
            // than count of want
            if (value
                > count.get(want))
                return "No";
 
            // Update the count of want
            // in the hash table
            if(count.has(want))
                    count.set(want, count.get(want)-value)
        }
 
    });
 
    // Return true if none of the
    // above cases satisfies
    return "Yes";
}
 
// Driver Code
var arr = [4, -2, 2, -4];
var N = 2;
var res = canReorderDoubled(arr);
// Print the result obtained
document.write(res);
 
 
</script>

Yes

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)