Candles Height

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Urban Company (UrbanClap)

Problem statement

Ninja is solving questions on an array in which he has given an integer ‘N’, representing the number of candles numbered through 1 to ‘N’. Initially, the height of all the candles is 0. There are ‘Q’ queries given to Ninja. In each query, Ninja has two integers, ‘L’, and ‘R’, and Ninja should increase the height for each candle by 1 from ‘L’ to ‘R’ both inclusive. Ninja can only perform ‘Q’ - 1 queries out of ‘Q’ given queries. Find the maximum count of candles having height ‘K’ after performing ‘Q’ - 1 queries.

For example: 
Let ‘N’ be: 2
Let queries be: [[1, 2], [1, 1]]
Let ‘K’ be: 1
Initial heights: [0, 0]
Removing query 1 and increasing heights in the range [1, 1] gives: [1, 0]. The number of candles having a height of 1 is 1.
Removing query 2 and increasing heights in the range [1, 2] gives: [1, 1]. The number of candles having a height of 1 is 2.
Hence, the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains three space-separated integers, ‘N’, ‘K’, and ‘Q’, representing the number of candles, the height of the candle needed, and the number of queries.

The next ‘Q’ lines of each test contain two space-separated integers, ‘L’ and ‘R’, representing the range for each query.
Output Format : 
For each test case, print a single integer representing the maximum count of the candle possible after performing ‘Q’ - 1 queries.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^6
1 <= Q <= 10^6
1 <= K <= Q
1 <= L <= R <= N

Time Limit: 1 sec
Sample Input 1 :
2
2 1 2
1 2
1 1
5 2 3
2 5
4 5
1 4
Sample Output 1 :
2
3
Explanation For Sample Input 1 :
For test case 1: 
Initial heights: [0, 0]
Removing query 1 and increasing heights in the range [1, 1] gives: [1, 0]. The number of candles having a height of 1 is 1.
Removing query 1 and increasing heights in the range [1, 2] gives: [1, 1]. The number of candles having a height of 1 is 2.
Hence, the answer is 2.


For test case 2: 
Initial heights: [0, 0, 0, 0, 0]
Removing query 1 and increasing heights in the range [4, 5] and [1, 4] gives: [1, 1, 1, 2, 1]. The number of candles having a height of 2 is 1.
Removing query 2 and increasing heights in the range [2, 5] and [1, 4] gives: [1, 2, 2, 2, 1]. The number of candles having a height of 2 is 3.
Removing query 3 and increasing heights in the range [2, 5] and [4, 5] gives: [0, 1, 1, 2, 2]. The number of candles having a height of 2 is 2.
Hence, the answer is 3.
Sample Input 2 :
2
5 5 2
1 2
2 5 
4 2 3
1 2
2 3
3 4
Sample Output 2 :
0
1
Hint

Try to heights naively using ‘Q’ - 1 queries at a time.

Approaches (2)
Brute Force

The basic idea is to run ‘Q’ - 1 queries by removing 1 query at a time. For each time, we find the number of candles with height equal to ‘K’ and find the maximum.
 

Here is the algorithm :
 

  1. Create a variable (say, ‘ANS’) that will store the maximum count and initialize it with 0.
  2. Run a loop from 0 to ‘Q’ (say, iterator ‘i’) that will run over all the queries.
    • Create a ‘CANDLE’ array to store the heights of the candles.
    • Run a loop from 0 to ‘Q’ (say, iterator ‘j’) that will run over all the queries by removing 1 query at a time.
      • Check if ‘j’ is not equal to ‘i’ to remove the ‘ith’ query
        • Update heights of candles from ‘L’ to ‘R’ for each ‘jth’ query.
    • Run a loop from 0 to ‘N’ (say, iterator ‘j’) to count the number of candles having heights equal to ‘K’ and store it in a variable (say, ‘CNT’).
    • Update ‘ANS’ by a maximum of ‘ANS’ and ‘CNT’.
  3. Finally, return ‘ANS’.
Time Complexity

O(N * (Q ^ 2)), where ‘N’ is the number of candles and ‘Q’ is the number of queries.
 

We run all the queries, and for each query, we iterate the queries again by removing one query at a time which takes O(Q ^ 2) time, and for each query, we update heights that can take O(N) of time. We also calculate the count of candles having heights ‘K’. Therefore, the overall time complexity will be O(N * (Q ^ 2)).

Space Complexity

O(N), where ‘N’ is the number of candles.

 

We create a ‘CANDLE’ array of size ‘N’ to store the heights. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Candles Height
Full screen
Console