KostasA KostasA - 2 months ago 8
Java Question

imrpove execution time in a simple java program

I am playing around codefight, but I am really stuck
to the following efficient issue.

Problem:

Given integers n, l and r, find the number of ways to represent n as a sum of two integers A and B such that l ≤ A ≤ B ≤ r.

Example:

For n = 6, l = 2 and r = 4, the output should be
countSumOfTwoRepresentations2(n, l, r) = 2.
There are just two ways to write 6 as A + B, where 2 ≤ A ≤ B ≤ 4: 6 = 2 + 4 and 6 = 3 + 3.

Here is my code. It passes all the unit tests but it failing
in the hidden ones. Can someone direct me somehow?
Thanks in advance.

public static int countSumOfTwoRepresentations2(int n, int l, int r) {
int nrOfWays = 0;
for(int i=l;i<=r;i++)
{
for(int j=i;j<=r;j++)
{
if(i+j==n)
nrOfWays++;
}
}
return nrOfWays;

}

Answer

Well, there's no need to make so huge calculations... It's easy to calculate:

public static int count(int n, int l, int r) {
    if (l > n/2)
        return 0;
    return Math.min(n/2 - l, r - n/2) + ((n%2 == 1) ? 0 : 1);
}

Passes all my tests so far. For positives and negatives as well.

Comments