Alex and his coins

2.8

4 votes
Math, C++, Observation, Basic Math
Problem

Alex loves to collect coins. He has been doing so since his childhood. He has a total of \(N\) different types of coins, numbered from \(0\) to \(N-1\). The \(i^{th}\) type has \(A[i]\) coins. Since, Alex is free right now, he wishes to keep these coins in order but in a specific way.

Initially no coins are in their place.

In one move, he can keep at most \(K[i]\) coins of the \(i^{th}\) type back in their place. Help him in finding the minimum number of moves it will take to re-order these coins.

Input Format:

  • The first line of input contains a single integer \(T\), which denotes the number of test cases.
  • The first line of each test case contains an integer \(N\), denoting the number of types of coins.
  • The second line of each test case contains \(N\) space-separated integers, where the \(i^{th}\) integer denotes the value of \(A[i]\).
  • The third line of each test case contains \(N\) space-separated integers, where the \(i^{th}\) integer denotes the value of \(K[i]\).

Output Format: For each test case, print an integer that denotes the minimum number of moves Alex will take to re-order coins.

Constraints:

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq A[i] \leq 10^9 \\ 1 \leq K[i] \leq 10^9\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:
In the first move, he keeps 3 coins of type 0, 1 coin of type 1, 3 of type 2, and 1 of type 3. So the remaining coins are {2, 0, 6, 1}.
In the second move, he keeps 2 coins of type 0, 3 of type 2, and 1 of type 3. So the remaining coins are {0, 0, 3, 0}.
In the third move, he keeps 3 coins of type 2. Now there are no remaining coins.
Hence, it takes him 3 moves to re-order.

For test case 2:
In the first move, he keeps 1 coin of type 0. Now there are no remaining coins.
Hence, it takes him 1 move to re-order.

Editor Image

?