Given an integer N which is always even, the task is to create an array of size N which contains N/2 even numbers and N/2 odd numbers. All the elements of array should be distinct and the sum of even numbers is equal to the sum of odd numbers. If no such array exists then print -1.
Examples:Â
Â
Input: N = 8Â
Output: 2 4 6 8 1 3 5 11Â
Explanation:Â
The array has 8 distinct elements which have equal sum of odd and even numbers, i.e., (2 + 4 + 6 + 8 = 1 + 3 + 5 + 11).
Input: N = 10Â
Output: -1Â
Explanation:Â
It is not possible to construct array of size 10.Â
Â
Â
Approach: To solve the problem mentioned above the very first observation is that it is not possible to create an array that has size N which is a multiple of 2 but not multiple of 4. Because, if that happens then the sum of one half which contains odd numbers will always be odd and the sum of another half which contains even numbers will always be even, hence the sum of both halves can’t be the same.
Therefore, the array which satisfies the problem statement should always have a size N which is a multiple of 4. The approach is to first construct N/2 even numbers starting from 2, which is the first half of the array. Then create another part of the array starting from 1 and finally calculate the last odd element such that it makes both the halves equal. In order to do so the last element of odd numbers should be (N/2) – 1 + N.
Below is the implementation of the above approach:Â
Â
CPP
// C++ program to Create an array// of size N consisting of distinct// elements where sum of odd elements// is equal to sum of even elementsÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to construct the required arrayvoid arrayConstruct(int N){Â
    // To construct first half,    // distinct even numbers    for (int i = 2; i <= N; i = i + 2)        cout << i << " ";Â
    // To construct second half,    // distinct odd numbers    for (int i = 1; i < N - 1; i = i + 2)        cout << i << " ";Â
    // Calculate the last number of second half    // so as to make both the halves equal    cout << N - 1 + (N / 2) << endl;}Â
// Function to construct the required arrayvoid createArray(int N){Â
    // check if size is multiple of 4    // then array exist    if (N % 4 == 0)Â
        // function call to construct array        arrayConstruct(N);Â
    else        cout << -1 << endl;}Â
// Driver codeint main(){Â
    int N = 8;Â
    createArray(N);Â
    return 0;} |
Java
// Java program to Create an array// of size N consisting of distinct// elements where sum of odd elements// is equal to sum of even elementsclass GFG{  // Function to construct the required arraystatic void arrayConstruct(int N){      // To confirst half,    // distinct even numbers    for (int i = 2; i <= N; i = i + 2)        System.out.print(i+ " ");      // To consecond half,    // distinct odd numbers    for (int i = 1; i < N - 1; i = i + 2)        System.out.print(i+ " ");      // Calculate the last number of second half    // so as to make both the halves equal    System.out.print(N - 1 + (N / 2) +"\n");}  // Function to construct the required arraystatic void createArray(int N){      // check if size is multiple of 4    // then array exist    if (N % 4 == 0)          // function call to conarray        arrayConstruct(N);      else        System.out.print(-1 +"\n");}  // Driver codepublic static void main(String[] args){    int N = 8;      createArray(N);}}Â
// This code is contributed by Princi Singh |
Python3
# python3 program to Create an array# of size N consisting of distinct# elements where sum of odd elements# is equal to sum of even elementsÂ
# Function to construct the required arraydef arrayConstruct(N):Â
    # To construct first half,    # distinct even numbers    for i in range(2, N + 1, 2):        print(i,end=" ")Â
    # To construct second half,    # distinct odd numbers    for i in range(1, N - 1, 2):        print(i, end=" ")Â
    # Calculate the last number of second half    # so as to make both the halves equal    print(N - 1 + (N // 2))Â
# Function to construct the required arraydef createArray(N):Â
    # check if size is multiple of 4    # then array exist    if (N % 4 == 0):Â
        # function call to construct array        arrayConstruct(N)Â
    else:        cout << -1 << endlÂ
# Driver codeif __name__ == '__main__':Â
    N = 8Â
    createArray(N)Â
# This code is contributed by mohit kumar 29 |
C#
// C# program to Create an array// of size N consisting of distinct// elements where sum of odd elements// is equal to sum of even elementsusing System;Â
class GFG{   // Function to construct the required arraystatic void arrayConstruct(int N){       // To confirst half,    // distinct even numbers    for (int i = 2; i <= N; i = i + 2)        Console.Write(i + " ");       // To consecond half,    // distinct odd numbers    for (int i = 1; i < N - 1; i = i + 2)        Console.Write(i + " ");       // Calculate the last number of second half    // so as to make both the halves equal    Console.Write(N - 1 + (N / 2) +"\n");}   // Function to construct the required arraystatic void createArray(int N){       // check if size is multiple of 4    // then array exist    if (N % 4 == 0)           // function call to conarray        arrayConstruct(N);       else        Console.Write(-1 +"\n");}   // Driver codepublic static void Main(String[] args){    int N = 8;       createArray(N);}}Â
// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to Create an array// of size N consisting of distinct// elements where sum of odd elements// is equal to sum of even elementsÂ
// Function to construct the required arrayfunction arrayConstruct(N){Â
    // To construct first half,    // distinct even numbers    for (let i = 2; i <= N; i = i + 2)        document.write(i + " ");Â
    // To construct second half,    // distinct odd numbers    for (let i = 1; i < N - 1; i = i + 2)        document.write(i + " ");Â
    // Calculate the last number of second half    // so as to make both the halves equal    document.write(N - 1 + (N / 2) + "<br>");}Â
// Function to construct the required arrayfunction createArray(N){Â
    // check if size is multiple of 4    // then array exist    if (N % 4 == 0)Â
        // function call to construct array        arrayConstruct(N);    else        document.write(-1 + "<br>");}Â
// Driver code    let N = 8;    createArray(N);Â
// This code is contributed by Surbhi Tyagi.</script> |
Output:Â
2 4 6 8 1 3 5 11
Â
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
