Создать массив заданного размера с равным количеством и суммой нечетных и четных чисел

Учитывая целое число N , задача состоит в том, чтобы найти массив длины N, который содержит одинаковое количество нечетных и четных элементов с равной суммой четных и нечетных элементов в массиве.
Примечание. Выведите -1, если такой массив невозможен.
Примеры:

Input: N = 4 
Output: 1 2 5 4 
Explanation: 
Even elements of the array – {2, 4}, S(even) = 6 
Odd elements of the array – {1, 5}, S(odd) = 6
Input: N = 6 
Output: -1 
Explanation: 
There are no such array which contains 3 even elements and 3 odd elements with equal sum. 
 

Подход: ключевое наблюдение в проблеме заключается в том, что только длина массива, кратная 4, может образовывать массив с равным количеством четных и нечетных элементов с одинаковой суммой. Ниже представлена иллюстрация шагов:

• Четные элементы массива - это первые N / 2 четных элементов натуральных чисел, начиная с 2.
• Точно так же (N / 2 - 1) нечетных элементов массива - это первые (N / 2 - 1) нечетные элементы натуральных чисел, начиная с 1.
• Последний нечетный элемент массива - это необходимое значение, чтобы сумма четных и нечетных элементов массива была равна.

   Последний нечетный элемент = 
     (сумма четных элементов) - 
     (сумма N / 2 - 1 нечетных элементов)

  Ниже представлена реализация описанного выше подхода:
  

  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 << " " ; 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 << " " ; } } // Driver Code int main() { int N = 8; findSolution(N); return 0; }

  Ява

  // 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 + " " ); 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( " " ); } } // 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 + " " ); 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( " " ); } } // 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>

  Выход:

   1 2 3 4 5 6 11 8

  Анализ производительности:
  

  • Сложность времени: O (N)
  • Вспомогательное пространство: O (1)

  Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

  Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.