Count the maximum number of numbers in an array whose sum is an even number
I have this code which, as I understand it, looks for the maximum number of consecutive numbers in a given array, which sum is an even number.
private static int f (int[]a, int low, int high)
{
int res = 0;
for (int i=low; i<=high; i++)
res += a[i];
return res;
}
public static int what (int []a)
{
int temp = 0;
for (int i=0; i<a.length; i++)
{
for (int j=i; j<a.length; j++)
{
int c = f(a, i, j);
if (c%2 == 0)
{
if (j-i+1 > temp)
temp = j-i+1;
}
}
}
return temp;
}
For example, the array [-3,4,8, -1,15] should return "4" and respond because -3 + 4 + 8-1 = 8 and 8 are even.
I need an idea on how to make it more efficient (+ what is efficiency now? O (n ^ 3)?)
Thanks in advance.
source to share
You only need one loop, which takes O (n).
You need to iterate through the array once and count the number of even numbers and the number of odd numbers. Your result evenCount + oddCount
if oddCount
even; evenCount + oddCount - 1
otherwise.
The reason for this is that the sum of all even numbers is even. The sum of each pair of odd numbers is also even, so an even sum with most of the elements has a number of elements, which is either the length of the array (if there is an even number of odd numbers) or the length of the array is 1 (if there is an odd number of odd numbers, in which case you must exclude one of them from the amount to get an even amount).
Actually, you only need to count the number of odd numbers:
public static int maxEvenSumLength (int []a)
{
int oddCount = 0;
for (int i=0; i<a.length; i++)
{
if (a[i] % 2 == 1) {
oddCount++;
}
}
return (oddCount % 2 == 0) ? a.length : (a.length - 1);
}
EDIT:
I missed the fact that items that have an even sum must be consecutive. In this case, if the number of odd numbers is even, the result is still the length of the array. The difference is that the number of odd numbers is odd. In this case, you must find the odd number closest to either end of the array, and the length of the consecutive even sum will be the number of elements up to the last odd number or after the first odd number (whichever is greater).
public static int maxConsecutiveEvenSumLength (int []a)
{
int oddCount = 0;
int firstOddIndex = -1;
int lastOddIndex = a.length;
for (int i=0; i<a.length; i++)
{
if (a[i] % 2 == 1) {
oddCount++;
if (firstOddIndex < 0)
firstOddIndex = i;
lastOddIndex = i;
}
}
if (oddCount % 2 == 0) {
return a.length;
} else {
return Math.max(a.length - firstOddIndex - 1,lastOddIndex);
}
}
We are still iterating once over the array, so the time complexity is still O (n).
source to share