# Hard Cash Codechef Solution

Hard Cash Codechef Solution: Chef wants to take Chefina on a date. However, he has to complete one more task before leaving. Since he does not want to be late, he is asking you for help.

There areÂ NNÂ bags with coins in a row (numberedÂ 11Â throughÂ NN); for each validÂ ii, theÂ ii-th bag containsÂ AiAiÂ coins. Chef should make the number of coins in each bag divisible by a given integerÂ KKÂ in the following way:

• choose an integerÂ ccÂ betweenÂ 00Â andÂ NNÂ (inclusive)
• take some coins from the firstÂ ccÂ bags â€• formally, for eachÂ iiÂ (1â‰¤iâ‰¤c1â‰¤iâ‰¤c), he may choose any number of coins betweenÂ 00Â andÂ AiAiÂ inclusive and take them out of theÂ ii-th bag
• move some of these coins to some of the lastÂ Nâˆ’cNâˆ’cÂ bags â€• formally, for eachÂ iiÂ (c+1â‰¤iâ‰¤Nc+1â‰¤iâ‰¤N), he may place a non-negative number of coins in theÂ ii-th bag

Of course, the number of coins placed in the lastÂ Nâˆ’cNâˆ’cÂ bags must not exceed the number of coins taken out from the firstÂ ccÂ bags, but there may be some coins left over. Letâ€™s denote the number of these coins byÂ RR. You should find the smallest possible value ofÂ RR.

### Input

• The first line of the input contains a single integerÂ TTÂ denoting the number of test cases. The description ofÂ TTÂ test cases follows.
• The first line of each test case contains two integersÂ NNÂ andÂ KK.
• The second line containsÂ NNÂ space-separated integersÂ A1,A2,â€¦,ANA1,A2,â€¦,AN.

### Output

For each test case, print a single line containing one integer â€• the smallest value ofÂ RR.

### Constraints

• 1â‰¤Tâ‰¤1031â‰¤Tâ‰¤103
• 1â‰¤Nâ‰¤1051â‰¤Nâ‰¤105
• 0â‰¤Aiâ‰¤1090â‰¤Aiâ‰¤109Â for each validÂ ii
• 1â‰¤Kâ‰¤1091â‰¤Kâ‰¤109
• the sum ofÂ NNÂ over all test cases does not exceedÂ 105105

```2
5 7
1 14 4 41 1
3 9
1 10 19
```

```5
3
```

### Explanation

Example case 1:Â One of the possible solutions is to chooseÂ c=4c=4, removeÂ 11,Â 00,Â 44Â andÂ 1313Â coins from bagsÂ 11,Â 22,Â 33Â andÂ 44Â respectively, and addÂ 1313Â coins to bagÂ 55.

Example case 2:Â The optimal solution is to chooseÂ c=3c=3Â and remove one coin from each bag.

## Hard Cash â€“ CodeChef Solution in JAVA

```import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 0; tc < T; ++tc) {
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < A.length; ++i) {
A[i] = sc.nextInt();
}
System.out.println(solve(A, K));
}
sc.close();
}
static int solve(int[] A, int K) {
return (int) (Arrays.stream(A).asLongStream().sum() % K);
}
}```

## Hard Cash â€“ CodeChef Solution in CPP

```#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n;
cin>>t;
while(t--){
long long k;
cin>>n>>k;
long long a[n];
for (int i=0; i<n; i++){
cin>>a[i];
}
long long ans = 0;
for (int i=0; i<n; i++){
ans += a[i];
}
ans = ans%k;
cout<<ans<<endl;
}
return 0;
}
```

## Hard Cash â€“ CodeChef Solution in Python

```t = int(input())
for _ in range(t):
n,k = map(int,input().split())
l = list(map(int,input().split()))
s = sum(l)
ans = s%k
print(ans)
```

Disclaimer:Â The above Problem (Hard CashÂ Â ) is generated byÂ CodeChef but the solution is provided byÂ Â Chase2learn.This tutorial is only forÂ EducationalÂ andÂ LearningÂ purpose.

Sharing Is Caring