CODEWITHSUNDEEP
javaarraysperformancesum
Alexy Grabov
Alexy Grabov

Reputation: 151

Count the maximum amount of numbers in an array which sum is an even number

I have this code, which, as I understand it, searches for the maximum amount of consecutive numbers in the 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" as and answer, because -3+4+8-1 = 8, and 8 is even.

I need an idea on how to make it more efficient (+what is it's efficiency now? O(n^3)? )

Thanks in advance.

Upvotes: 4

Views: 1744

Answers (1)

Eran
Eran

Reputation: 393856

You only need a single loop, which would take O(n).

You need to iterate over the array once and count the number of even numbers and the number of odd numbers. Your output is evenCount + oddCount if oddCount is even, and evenCount + oddCount - 1 otherwise.

The reason for that is that the sum of all even numbers is even. The sum of each pair of odd numbers is also even, so the even sum with the most elements has a number of elements which is either the length of the array (if there's an even number of odd numbers), or the length of the array - 1 (if there's an odd number of odd numbers, in which case you have to exclude one of them from the sum to get an even sum).

Actually, you only have 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 the elements having an even sum should be consecutive. In that case, if the number of odd numbers is even, the result is still the length of the array. The difference is when the number of odd numbers is odd. In that case you should find the odd number closest to either ends of the array, and the length of the consecutive even sum would be the number of elements before the last odd number or after the first odd number (the larger of the two).

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).

Upvotes: 3

Related Questions