# Equal Operation | hackerearth solution

Problem

You are given an array $�$ containing $�$ integers. You can apply the following operation on the array:

• Choose an index $�\phantom{\rule{thickmathspace}{0ex}}\left(1\le �\le \mid �\mid \right)$, split ${�}_{�}$ into two positive integers $�,�$ such that ${�}_{�}=�+�$, remove the ${�}^{�\mathrm{â„Ž}}$ element from the array and append the elements $�,�$ to the array.

Find the minimum number of operations required to make all integers of the array equal.

Input format

• The first line contains $�$ denoting the number of test cases. The description of $�$ test cases is as follows:
• For each test case:
• The first line contains a single integer $�$ denoting the size of array $�$.
• The second line contains $�$ integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$ - denoting the elements of $�$.

Output format
For each test case, print the minimum number of operations required to make all integers of the array equal.

Constraints

$1\le �\le {10}^{4}\phantom{\rule{0ex}{0ex}}1\le �\le {10}^{5}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}1\le {�}_{�}\le {10}^{9}\phantom{\rule{0ex}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}��\phantom{\rule{thickmathspace}{0ex}}�\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}�����\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}������\phantom{\rule{thickmathspace}{0ex}}2\cdot {10}^{5}.$

Sample Input
2
2
2 4
3
1 2 3
Sample Output
1
3

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

Test case 1: Choose i = 2 and split A[2] = 4 into X = 2, Y = 2 making A = [2, ,2, 2]. Now all elements of the array are equal.

Test case 2:

• Choose i = 2 and split A[2] = 2 into X = 1, Y = 1 making A = [1, 3, 1, 1].
• Choose i = 2 and split A[2] = 3 into X = 2, Y = 1 making A = [1, 1, 1, 2, 1].
• Choose i = 4 and split A[4] = 2 into X = 1, Y = 1 making A = [1, 1, 1, 1, 1, 1]. Now all elements of the array are equal.

Code(C++):-

#include <iostream>

using namespace std;

template <typename T> inline void inp (T &n) {
n = 0;
int ch = getchar_unlocked (), sign = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1; // only if also negative integer
ch = getchar_unlocked ();
}
while (ch >= '0' && ch <= '9')
n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked ();
n *= sign; // only if also negative integer
}
inline int inp () {
int n = 0;
int ch = getchar_unlocked (), sign = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1; // only if also negative integer
ch = getchar_unlocked ();
}
while (ch >= '0' && ch <= '9')
n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked ();
n *= sign; // only if also negative integer
return n;
}
template <typename T> inline void puti (T n, char lc) {
if (0 == n) {
putchar_unlocked ('0');
if (lc) putchar_unlocked (lc);
return;
}
bool sign = false;
if (n < 0) sign = true, n = -n;
char s[20]; int rdi =-1;
while (n) {
s [++rdi] = '0' + n % 10;
n /= 10;
}
if (sign) putchar_unlocked ('-');
while (rdi >= 0) putchar_unlocked (s [rdi--]);
if (lc) putchar_unlocked (lc);
}
inline void puts (string s) {
for (char c : s) putchar_unlocked (c);
}
inline void inps (string &i) {
i = "";
char c = getchar_unlocked ();
while (c < 32 or c > 127) c = getchar_unlocked ();
while (c >= 32 and c <= 127) i += c, c = getchar_unlocked ();
}
inline string inps () {
string i = "";
char c = getchar_unlocked ();
while (c < 32 or c > 127) c = getchar_unlocked ();
while (c >= 32 and c <= 127) i += c, c = getchar_unlocked ();
return i;
}
inline void inpc (char &c) {
c = getchar_unlocked ();
if (c == EOF) return;
while (c < 32 or c > 127) c = getchar_unlocked ();
}
inline char inpc () {
char c = getchar_unlocked ();
if (c == EOF) return c;
while (c < 32 or c > 127) c = getchar_unlocked ();
return c;
}
int main (){
int n, t, i, mn, rest;
long long ops;
bool nok;
inp (t);
while (t--) {
inp (n);
int a [n];
for (i = 0; i < n; i++) inp (a [i]);
mn = a [0];
nok = true;
while (nok) {
ops = 0;
nok = false;
for (auto v : a) {
ops += v / mn - 1;
rest = v % mn;
if (rest) {
mn = rest;
nok = true;
break;
}
}
}
puti (ops, '\n');
}
}

Code(JAVA):-

import java.util.*;
import java.io.*;
public class TestClass {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new PrintWriter(System.out)));
StringBuilder sb = new StringBuilder();
while (t --> 0) {
int arr[] = new int[n];
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
int gcd = arr[0];
for (int x : arr) gcd = gcd(gcd, x);
long ans = 0;
for (int x : arr) ans += (x - gcd) / gcd;
sb.append(ans).append("\n");
}
pw.println(sb.toString().trim());
pw.close();
br.close();
}
public static int gcd(int x, int y) {
if (x == 0) return y;
return gcd(y % x, x);
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-