Optimal Denomination | CodeChef Solution

Hello coders, today we are going to solve Optimal Denomination CodeChef Solution whose Problem Code is MINNOTES.

Task

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 N employees, where the i-th employee has salary A_i. 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.

Input

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer N.
• The second line contains N integers A1, A2, . . . , AN, where A_i is the salary of the i-th employee.

Output

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

Constraints

• 1 ≤ T ≤ 12⋅10⁴
• 1 ≤ N ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹
• The sum of N over all test cases is at most 10⁶.

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 1: We can change the salary of the third person to 1 and use 1 as the denomination. So in total we need 1/1 + 2/1 + 1/1 = 1 + 2 + 1 = 4 notes.

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

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

Solution – Optimal Denomination

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;
}

Python

from math import gcd


j = []
j = [0]*100
j.pop()
j.pop()
j.append(99)
j.pop()
j.sort()
j.append(1000)
j.sort()

for _ in range(int(input())):
    ans = float('inf')
    n = int(input())
    l = list(map(int,input().split()))
    if n==1: print(1);continue
    sumo = 0
    for i in l:
        sumo+=i 
    
    bwd = [l[-1]]
    fwd = [l[0]]
    
    

    for i in range(n-2,-1,-1):
        bwd.append(gcd(bwd[-1],l[i]))
    bwd = bwd[::-1]

    for i in range(1,n):
        fwd.append(gcd(fwd[i-1],l[i]))
    
    main_arr = [1]*(n)
    main_arr[0] = bwd[1]
    main_arr[n-1] = fwd[-2]

    for i in range(1,n-1):
        main_arr[i]= gcd(bwd[i+1],fwd[i-1])

    

    for i in range(n):
        tmp = (sumo - l[i]+main_arr[i])//main_arr[i]
        ans = min(ans,tmp)

    print(ans)

Java

import java.util.*;
import java.io.*;


class Main{
    public static void main (String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int size = (int)1e6;
        long[] arr = new long[size];
        long[] tmp1 = new long[size];
        long[] tmp2 = new long[size];

        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            int n = Integer.parseInt(in.readLine());
            long sum = 0, d = 0;
            String[] input = in.readLine().split(" ");
            for (int i=1; i<=n; i++)
                arr[i] = Long.parseLong(input[i-1]);
                
            Arrays.sort(arr, 1, n+1);
            
            tmp1[1] = arr[1];
            tmp2[n] = arr[n];
            
            for (int i=1; i<=n; i++)
                tmp1[i] = GCD(tmp1[i-1], arr[i]);
            for (int i=n-1; i>=1; i--)
                tmp2[i] = GCD(tmp2[i+1], arr[i]);

            for (int i=1; i<=n; i++)
                sum += arr[i];
                
            long count = Long.MAX_VALUE;
            
            for (int i=1; i<=n; i++){
                d = (sum - arr[i] + GCD(tmp1[i-1], tmp2[i+1])) / GCD(tmp1[i-1], tmp2[i+1]);
                if (d < count)
                    count = d;
            }
            System.out.println(count);
        }
        in.close();
    }
    public static long GCD(long a, long b){
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }
}

Disclaimer: The above Problem (Optimal Denomination) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.