Page Contents

*Optimal Denomination Codechef Solution*

*Optimal Denomination Codechef Solution*

You are the owner of a big company. You are so rich, that the government has allowed you to print as many notes as you want of any single value that you like. You also have peculiar behavioral traits and you often do things that look weird to a third person.

You have NN employees, where the ii-th employee has salary AiAi. You want to pay them using a denomination that you create. You are also eco-friendly and wish to save paper. So, you wish to pay them using as few notes as possible. Find out the minimum number of notes required if you can alter the salary of at most one employee to any **positive integer** that you like, and choose the positive integer value that each note is worth (called its denomination).

Each employee must receive the exact value of his/her salary and no more.

See Also : July Long Challenge 2021 Solutions Codechef

### Input

- The first line contains an integer TT, the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer NN.
- The second line contains NN integers A1,A2,…,ANA1,A2,…,AN, where AiAi is the salary of the ii-th employee.

### Output

For each test case, output in a single line the answer to the problem.

### Constraints

- 1≤T≤12⋅1041≤T≤12⋅104
- 1≤N≤1051≤N≤105
- 1≤Ai≤1091≤Ai≤109
- The sum of NN over all test cases is at most 106106.

### Subtasks

**Subtask #1 (100 points):** Original constraints

### Sample Input

```
3
3
1 2 3
3
8 4 2
2
2 2
```

### Sample Output

```
4
4
2
```

### Explanation

**Test Case 11:** We can change the salary of the third person to 11 and use 11 as the denomination. So in total we need 11+21+1111+21+11 = 1+2+11+2+1 = 44 notes.

**Test Case 22:** We can change the salary of the first person to 22 and use 22 as the denomination. So in total we need 1+2+11+2+1 = 44 notes.

**Test Case 33:** We can use 22 as the denomination and we need not change the salary of any person. So in total we need 1+11+1 = 22 notes.

*Solution*

*Solution*

*Program C++:*

```
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int a[N],f[N],b[N];
void gcdc(int n)
{
f[1]=a[1];b[n]=a[n];
for(int i=n-1;i>0;i--)
{
b[i]=__gcd(b[i+1],a[i]);
}
for(int i=2;i<n+1;i++)
{
f[i]=__gcd(f[i-1],a[i]);
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int sum=0;
int ans=0;
for(int i=1;i<n+1;i++)
{
cin>>a[i];
}
sort(a,a+n+1);
gcdc(n);
for(int i=1;i<n+1;i++)
{
sum+=a[i];
}
int mn=LLONG_MAX;
for(int i=1;i<n+1;i++)
{
ans=(sum-a[i]+__gcd(f[i-1],b[i+1]))/__gcd(f[i-1],b[i+1]);
if(ans<mn)
mn=ans;
}
cout<<mn<<"\n";
}
return 0;
}
```

*July Long Challenge 2021 Solutions*

*July Long Challenge 2021 Solutions*

*Maximum Production**Relativity**XxOoRr**Optimal Denomination**K Path Query**Chef vs Bharat**Chef and Pairs**Even Odd Partition**Dakimakura Distribition**Madoka and Ladder Decomposition*

*Weekly Contest 247*

*Weekly Contest 247*

- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony

*Biweekly Contest 55*

*Biweekly Contest 55*

- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System

This is a great tip particularly to those new to the blogosphere.

Simple but very precise info… Appreciate your sharing this one.

A must read post!