Generate an array of given size with equal count and sum of odd and even numbers
Given an integer N, the task is to find an array of length N that contains same count of odd and even elements with an equal sum of even and odd elements in the array.
Note: Print -1 if no such array is possible.
Examples:
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.
Approach: The key observation in the problem is that only the length of an array which is a multiple of 4 can form an array with an equal number of even and odd elements with equal sum. Below is the illustration of the steps:
- Even elements of the array is the first N/2 even elements of the natural numbers starting from 2.
- Similarly, (N/2 – 1) odd elements of the array is the first (N/2 – 1) odd elements of the natural numbers starting from 1.
- The Last odd element of the array is the required value to make the sum of the even and odd elements of the array equal.
Last Odd Element =
(sum of even elements) -
(sum of N/2 - 1 odd elements) - Below is the implementation of the above approach:
-
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>
-
Output
1 2 3 4 5 6 11 8
- Performance Analysis:
-
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Contact Us