Ninja And The Apples

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
NI (National Instruments)

Problem statement

Ninja has been given two baskets of apples containing ‘A’ and ‘B’ apples each. Also, he has been given extra ‘C’ apples separately.

This apple will be gifted to the Ninja’s best buddies; Ninja wants to do some partiality so that the number of apples in the first basket is strictly greater than the number of apples in the second basket.

The ninja can do it using extra ‘C’ apples, he must have to use all the extra apples and transfer them in both the first and second basket.

Your task is to help Ninja by calculating a number of possible arrangements of apples so that the resultant configuration is feasible for Ninja to do the partiality.

EXAMPLE: 
Input: 'A' = 5, 'B' = 3, 'C' = 4

Output: 3

Here only three possible combinations are:

(7, 5) Transfer 2 apples to the first basket and 2 apples to the second basket.
(9, 3) Transfer 4 apples to the first basket and 0 apples to the second basket.
(8, 4) Transfer 3 apples to the first basket and 1 apple to the second basket.

Only above combinations for (A, B) satisfies the condition that all 'C'  apples are used and ('A' > 'B')
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain integer 'T' denoting the number of test cases. For each test case, there will be a single line containing three integers 'A', 'B', and 'C' only.
Output format : 
For each test case, print a single line containing a single integer number of possible arrangements of apples so that the resultant configuration is feasible for Ninja to do the partiality.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10^5
0 <= 'A', 'B', 'C'<= 10^8

Time Limit : 1 sec
Sample Input 1 :
2
10 6 4
2 1 0
Sample Output 1 :
4
1
Explanation Of Sample Input 1 :
For the first test case, only three possible combinations are:

(11, 9) Transfer 1 apple to the first basket and 3 apples to the second basket.
(12, 8) Transfer 2 apples to the first basket and 2 apples to the second basket.
(14, 6) Transfer 4 apples to the first basket and 0 apples to the second basket.
(13, 7) Transfer 3 apples to the first basket and 1 apple to the second basket.

Only above combinations for (A, B) satisfies the condition for all 'C' are used and ('A' > 'B')

For the second test case only one combination (2, 1) is possible because there are no extra apples.
Sample Input 2 :
2
3 5 5
4 10 6
Sample Output 2 :
2
0
Hint

Can you try to derive the formula for an answer?

Approaches (1)
Maths

Approach: 

 

  • Say 'U' and 'V' be the number of apples transferred to the first and second basket respectively.
  • 'A' + 'U' > 'B' + 'V' must be satisfied.
  • 'A' + 'U' > 'B' + ('C' - 'U')
  • 'U' > ('C' - 'A' + 'B')/2
  • Since 'U' can't be negative
  • 'U' > max(0, ('C' - 'A' + 'B')/2)
  • Since 'U' > max(0, ('C' - 'A' + 'B')/2) we can assume 'U' = max(0, ('C' - 'A' + 'B')/2 + 1).
  • Let 'P' will be the minimum possible value of 'U'. 'P' = 'max(0, ('C' - 'A' + 'B' + 2)/2)'.
  • Return 'max(0, 'C' - 'P' + 1).

 

Algorithm :  
 

  1. Initialize the integer 'P' = 'max(0, ('C' - 'A' + 'B' + 2)/2)'
  2. Return 'max(0, 'C' - 'P' + 1).
Time Complexity

O(1)
 

As all the operations are constant time, the time complexity will be O(1).

Space Complexity

O(1)
 

As we are using the constant extra space, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja And The Apples
Full screen
Console