[Codefights] Count Sum of Two Representations 2

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.


 

Solution

[0, [n/2-l, r-n/2].min + (n+1)%2].max
(i.e. Max( 0 , Min(n/2-l, r-n/2) + (n+1)%2 ) )

Explanation

We can solve this problem with a loop, but there is a “simpler” or “shorter” way.

Without a given range, the number of ways to represent the sum of n can be determined by n/2

n => # ways
2 => 1 … (1, 1)
3 => 1 … (1, 2)
4 => 2 … [(1,3), (2, 2)]
5 => 2 … [(1,4), (2,3)]
6 => 3 … [(1,5), (2,4), (3,4)]

However, we are looking for the number of ways to represent within a range of lower bound, l, and higher bound, r.

If we only had a lower bound, we would have…
(n/2 – l) + (n+1)%2

  • n/2 – l => l ways less than the total # of ways because we used to start at 1, but now we start at l
  • (n+1)%2 => +1 if n is even, +0 if odd
n = 6
l = 2

n/2 - l = 1
(n+1)%2 = 1

# ways = 1 + 1 = 2
Proof: [(2,4),(3,3)]

If we only had a higher bound, we would have…
(r – n/2) + (n+1)%2 with similar explanation as above

Now, we have both the lower and the higher bound.
So we take the minimum between the two. Meaning, we are taking the “stricter” bound.
Min(n/2 – l , r – n/2) + (n+1)%2

Since # of ways cannot be negative, our answer would be
Max(0, Min(n/2 – l , r – n/2) + (n+1)%2)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s