Header Ads Widget

Equal Operation | hackerearth solution

Rajnish Tripathi 21:50
Problem

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

  • Choose an index �(1≤�≤∣�∣), split �� into two positive integers �,� such that ��=�+�, remove the ��ℎ 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,…,�� - 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≤�≤1041≤�≤1051≤��≤109�����������������������������������2⋅105.

 

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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new PrintWriter(System.out)));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t --> 0) {
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments