Sum of Absolutes
I was trying to solve a simple problem posted on HackerRank.
https://www.hackerrank.com/contests/w16/challenges/sum-of-absolutes
I solved the problem, however its getting a timeout error for those with an input array of size 100000. Can anyone help me optimize this code below so that it doesn't overheat.
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print outputto STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int n= in.nextInt();
int q = in.nextInt();
in.nextLine();
int[] a = new int[n+1];
for(int i=1;i<=n;i++)
{
a[i]= in.nextInt();
}
for(int j=0;j<q;j++)
{
int l = in.nextInt();
int r = in.nextInt();
int sum=0;
for(int k=l;k<=r ;k++)
{
sum = Math.abs(sum+a[k]);
}
if(sum%2 == 0)
System.out.println("Even");
else
System.out.println("Odd");
}
}
source to share
I think you need to completely rethink your solution: you really don't need to design summation to establish whether the result is odd or even.
Observing that adding two even numbers or two odd numbers gives you an even; and that adding even and odd gives you an odd value for all numbers (positive and negative) should be all you need.
source to share
Consider if there is a shortcut that will give you the same odd / even answer. For example, -8 and 8 are both uniform, and -3 and 3 are odd. Do you really need to take an absolute value to determine if the sum is even or odd?
--- Edit: Another thought or two ---
First thought. Have a look at Bitwise and Bit Change Operations . There are bitwise ways to find out if a number is negative (namely, the most significant bit is 1). And there are bitwise ways to determine if a number is odd (namely, the least significant bit of a positive number is 1, and the least significant bit of a negative number is 0).
--- Edit: Second thought ---
Could you shrink the array without storing the input numbers, but instead the parity of those numbers? For example, you can use boolean[] isOdd
or BitSet isOdd
? You can store -7 in position i as isOdd[i] = true;
or isOdd.set(i);
. (Since BitSet and boolean both initialize to all false, you would not change the boolean or BitSet at position j if position j was even, see BitSet .) Then your answer will be to count the odds (or translate boolean or nothing) in the requested set and the answer to odd if the amount was odd (or false or 0) or even if the amount was even (or true or 1).
Why should you use BitSet or boolean array? You can pack more information into less memory, making it easier for Java to find space and leading to fewer page faults if you go over a page border.
source to share