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;
}
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.