Genere una array de tamaño dado con el mismo recuento y suma de números pares e impares

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar una array de longitud N que contenga la misma cantidad de elementos pares e impares con una suma igual de elementos pares e impares en la array.
Nota: Imprima -1 si tal array no es posible. 
Ejemplos: 
 

Entrada: N = 4 
Salida: 1 2 5 4 
Explicación: 
Elementos pares de la array: {2, 4}, S (par) = 6 
Elementos impares de la array: {1, 5}, S (impar) = 6
Entrada : N = 6 
Salida: -1 
Explicación: 
No existe tal array que contenga 3 elementos pares y 3 elementos impares con la misma suma. 
 

Enfoque: La observación clave en el problema es que solo la longitud de una array que es un múltiplo de 4 puede formar una array con el mismo número de elementos pares e impares con la misma suma. A continuación se muestra la ilustración de los pasos: 
 

  • Los elementos pares de la array son los primeros N/2 elementos pares de los números naturales a partir de 2.
  • Del mismo modo, (N/2 – 1) elementos impares de la array son los primeros (N/2 – 1) elementos impares de los números naturales a partir del 1.
  • El último elemento impar de la array es el valor requerido para que la suma de los elementos pares e impares de la array sea igual. 
    Last Odd Element = 
   (sum of even elements) - 
   (sum of N/2 - 1 odd elements)

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

    C++

    // C++ implementation to find the
    // array containing same count of
    // even and odd elements with equal
    // sum of even and odd elements
      
    #include <bits/stdc++.h>
      
    using namespace std;
      
    // Function to find the array such that
    // the array contains the same count
    // of even and odd elements with equal
    // sum of even and odd elements
    void findSolution(int N)
    {
      
        // Length of array which is not
        // divisible by 4 is unable to
        // form such array
        if (N % 4 != 0)
            cout << -1 << "\n";
        else {
            int temp = 0, sum_odd = 0,
                sum_even = 0;
            int result[N] = { 0 };
      
            // Loop to find the resulted
            // array containing the same
            // count of even and odd elements
            for (int i = 0; i < N; i += 2) {
                temp += 2;
      
                result[i + 1] = temp;
                // Find the total sum
                // of even elements
                sum_even += result[i + 1];
      
                result[i] = temp - 1;
                // Find the total sum
                // of odd elements
                sum_odd += result[i];
            }
      
            // Find the difference between the
            // total sum of even and odd elements
            int diff = sum_even - sum_odd;
      
            // The difference will be added
            // in the last odd element
            result[N - 2] += diff;
      
            for (int i = 0; i < N; i++)
                cout << result[i] << " ";
            cout << "\n";
        }
    }
      
    // Driver Code
    int main()
    {
        int N = 8;
        findSolution(N);
        return 0;
    }

    Java

    // Java implementation to find the
    // array containing same count of
    // even and odd elements with equal
    // sum of even and odd elements
      
    class GFG{
      
    // Function to find the array such that
    // the array contains the same count
    // of even and odd elements with equal
    // sum of even and odd elements
    static void findSolution(int N)
    {
      
        // Length of array which is not
        // divisible by 4 is unable to
        // form such array
        if (N % 4 != 0)
            System.out.print(-1 + "\n");
      
        else 
        {
            int temp = 0, sum_odd = 0;
            int sum_even = 0;
            int result[] = new int[N];
      
            // Loop to find the resulted
            // array containing the same
            // count of even and odd elements
            for(int i = 0; i < N; i += 2)
            {
               temp += 2;
               result[i + 1] = temp;
                 
               // Find the total sum
               // of even elements
               sum_even += result[i + 1];
               result[i] = temp - 1;
                 
               // Find the total sum
               // of odd elements
               sum_odd += result[i];
            }
              
            // Find the difference between the
            // total sum of even and odd elements
            int diff = sum_even - sum_odd;
      
            // The difference will be added
            // in the last odd element
            result[N - 2] += diff;
      
            for(int i = 0; i < N; i++)
               System.out.print(result[i] + " ");
            System.out.print("\n");
        }
    }
      
    // Driver Code
    public static void main(String[] args)
    {
        int N = 8;
        findSolution(N);
    }
    }
      
    // This code is contributed by Amit Katiyar

    Python3

    # Python3 implementation to find the 
    # array containing same count of 
    # even and odd elements with equal 
    # sum of even and odd elements 
      
    # Function to find the array such that 
    # the array contains the same count 
    # of even and odd elements with equal 
    # sum of even and odd elements 
    def findSolution(N): 
      
        # Length of array which is not 
        # divisible by 4 is unable to 
        # form such array 
        if (N % 4 != 0): 
            print(-1) 
        else: 
            temp = 0
            sum_odd = 0
            sum_even = 0
            result = [0] * N 
      
            # Loop to find the resulted 
            # array containing the same 
            # count of even and odd elements 
            for i in range(0, N, 2): 
                temp += 2
                result[i + 1] = temp 
                  
                # Find the total sum 
                # of even elements 
                sum_even += result[i + 1] 
                result[i] = temp - 1
                  
                # Find the total sum 
                # of odd elements 
                sum_odd += result[i] 
      
            # Find the difference between the 
            # total sum of even and odd elements 
            diff = sum_even - sum_odd 
      
            # The difference will be added 
            # in the last odd element 
            result[N - 2] += diff 
              
            for i in range(N): 
                print(result[i], end = " ") 
            print() 
      
    # Driver Code 
    N = 8; 
    findSolution(N)
          
    # This code is contributed by divyamohan123 

    C#

    // C# implementation to find the
    // array containing same count of
    // even and odd elements with equal
    // sum of even and odd elements
    using System;
      
    class GFG{
      
    // Function to find the array such that
    // the array contains the same count
    // of even and odd elements with equal
    // sum of even and odd elements
    static void findSolution(int N)
    {
      
        // Length of array which is not
        // divisible by 4 is unable to
        // form such array
        if (N % 4 != 0)
            Console.Write(-1 + "\n");
      
        else
        {
            int temp = 0, sum_odd = 0;
            int sum_even = 0;
            int []result = new int[N];
      
            // Loop to find the resulted
            // array containing the same
            // count of even and odd elements
            for(int i = 0; i < N; i += 2)
            {
               temp += 2;
               result[i + 1] = temp;
                 
               // Find the total sum
               // of even elements
               sum_even += result[i + 1];
               result[i] = temp - 1;
                 
               // Find the total sum
               // of odd elements
               sum_odd += result[i];
            }
              
            // Find the difference between the
            // total sum of even and odd elements
            int diff = sum_even - sum_odd;
      
            // The difference will be added
            // in the last odd element
            result[N - 2] += diff;
      
            for(int i = 0; i < N; i++)
               Console.Write(result[i] + " ");
            Console.Write("\n");
        }
    }
      
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 8;
        findSolution(N);
    }
    }
      
    // This code is contributed by Rohit_ranjan

    JavaScript

    <script>
      
    // JavaScript implementation to find the
    // array containing same count of
    // even and odd elements with equal
    // sum of even and odd elements
      
      
    // Function to find the array such that
    // the array contains the same count
    // of even and odd elements with equal
    // sum of even and odd elements
    function findSolution(N)
    {
      
        // Length of array which is not
        // divisible by 4 is unable to
        // form such array
        if (N % 4 != 0)
            document.write(-1 + "<br>");
        else {
            let temp = 0, sum_odd = 0,
                sum_even = 0;
            let result = new Uint8Array(N);
      
            // Loop to find the resulted
            // array containing the same
            // count of even and odd elements
            for (let i = 0; i < N; i += 2) {
                temp += 2;
      
                result[i + 1] = temp;
                // Find the total sum
                // of even elements
                sum_even += result[i + 1];
      
                result[i] = temp - 1;
                // Find the total sum
                // of odd elements
                sum_odd += result[i];
            }
      
            // Find the difference between the
            // total sum of even and odd elements
            let diff = sum_even - sum_odd;
      
            // The difference will be added
            // in the last odd element
            result[N - 2] += diff;
      
            for (let i = 0; i < N; i++)
                document.write(result[i] + " ");
            document.write("<br>");
        }
    }
      
    // Driver Code
        let N = 8;
        findSolution(N);
      
      
      
    // This code is contributed by Surbhi Tyagi.
    </script>
    Producción: 

    1 2 3 4 5 6 11 8

     

    Análisis de rendimiento: 
     

    • Complejidad de tiempo: O(N)
    • Espacio Auxiliar: O(1)

     

Publicación traducida automáticamente

Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *