Number of operations such that size of the Array becomes 1
Given an array A[] of N positive integers. The task is to find the number of operations such that the size of the array becomes 1 at the end of operations. The operation to be performed is:
- In the current array, let X be the maximum element and Y be the minimum element. Let Z=X%Y. If Z is 0, remove X from the array, else replace X with Z.
- Note that after each operation the size of the array either remains the same or gets reduced by 1.
Examples:
Input: N = 3, A[] = {2, 3, 6}
Output: 3
Explanation: Following are the course of operations –
1st operation -> X = 6, Y = 2. Z = X%Y = 0. Hence, we delete X=6 (i.e. 3rd element) from the array. A[] becomes {2, 3}.
2nd operation -> X = 3, Y = 2. Z =X%Y = 1. Hence, we replace X with Z. A[] becomes {2, 1}.
3rd operation -> X = 2, Y = 1. Z = X%Y = 0. Hence, we delete X=2(i.e. first element) from the array. A[] becomes {1}.
It can be seen that length of array has become 1 after 3 operations.Input: N = 6, A[] = {1232, 452, 23491, 34099, 57341, 21488}
Output: 12
Approach: To solve the problem follow the below idea:
The idea is to use the set data structure to store the unique elements in the given array and repeatedly find the largest and smallest elements of the set using the end() and begin() functions, respectively. Then calculate the modulus of the largest and smallest elements, and insert the result into the set if the value of Z is not zero.
Below are the steps for the above approach:
- Declare a set S.
- Insert all the elements of array A[] into the S.
- Initialize a variable (say “ans”) with 0, that stores the total number of operations.
- Perform steps 5 to 9, till the size of set S becomes 1.
- Store the element from the beginning and end of the set in variables Y and X respectively.
- Find Z=X%Y.
- If Z is non-zero, insert it into the set.
- Erase X from the set.
- Increment “ans” in each operation.
- Return the ans.
Below is the code for the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to find the number of // operations such that size of the // array becomes 1 int totalOperations( int N, int A[]) { // Declaring a set set< int > S; // Inserting all the elements of // array into the set for ( int i = 0; i < N; i++) { S.insert(A[i]); } // Initializing ans with 0 to store // the total operations int ans = 0; // Perform the operation, till size // of the set becomes 1 while (S.size() > 1) { // Find the smallest and largest // elements of the array. i.e // first and last element of // the set auto End = S.end(); auto Start = S.begin(); End--; int X = *End; int Y = *Start; // Calculate Z, i.e. X%Y int Z = X % Y; // If Z is non-zero, insert it // into the set if (Z) { S.insert(Z); } // Erase X from the set S.erase(S.find(X)); // Increment ans, i.e. the number // of operations performed ans++; } // return answer return ans; } // Driver code int32_t main() { int N = 3; int A[] = { 2, 3, 6 }; int answer = totalOperations(N, A); // Function Call cout << answer << endl; return 0; } |
Java
import java.util.*; public class Main { static long totalOperations( int N, int [] A) { // Declaring a set Set<Integer> S = new HashSet<Integer>(); // Inserting all the elements of // array into the set for ( int i = 0 ; i < N; i++) { S.add(A[i]); } // Initializing ans with 0 to store // the total operations long ans = 0 ; // Perform the operation, till size // of the set becomes 1 while (S.size() > 1 ) { // Find the smallest and largest // elements of the array. i.e // first and last element of // the set int X = Collections.max(S); int Y = Collections.min(S); // Calculate Z, i.e. X%Y int Z = X % Y; // If Z is non-zero, insert it // into the set if (Z != 0 ) { S.add(Z); } // Erase X from the set S.remove(X); // Increment ans, i.e. the number // of operations performed ans++; } // return answer return ans; } public static void main(String[] args) { int N = 3 ; int [] A = { 2 , 3 , 6 }; long answer = totalOperations(N, A); // Function Call System.out.println(answer); } } //This code is contributed by tushar rokade |
Python3
# Importing the required module import math # Function to find the number of # operations such that size of the # array becomes 1 def totalOperations(N, A): # Declaring a set S = set () # Inserting all the elements of # array into the set for i in range (N): S.add(A[i]) # Initializing ans with 0 to store # the total operations ans = 0 # Perform the operation, till size # of the set becomes 1 while len (S) > 1 : # Find the smallest and largest # elements of the array. i.e # first and last element of # the set X = max (S) S.remove(X) Y = min (S) # Calculate Z, i.e. X%Y Z = X % Y # If Z is non-zero, insert it # into the set if Z ! = 0 : S.add(Z) # Increment ans, i.e. the number # of operations performed ans + = 1 # return answer return ans # Driver code if __name__ = = '__main__' : N = 3 A = [ 2 , 3 , 6 ] answer = totalOperations(N, A) # Function Call print (answer) |
C#
// C# code for the above appraoch: using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to find the number of operations such that // size of the array becomes 1 static long totalOperations( int N, int [] A) { // Declaring a set HashSet< int > S = new HashSet< int >(); // Inserting all the elements of array into the set for ( int i = 0; i < N; i++) { S.Add(A[i]); } // Initializing ans with 0 to store the total // operations long ans = 0; // Perform the operation, till size of the set // becomes 1 while (S.Count() > 1) { // Find the smallest and largest elements of the // array. i.e first and last element of the set int X = S.Max(); int Y = S.Min(); // Calculate Z, i.e. X%Y int Z = X % Y; // If Z is non-zero, insert it into the set if (Z != 0) { S.Add(Z); } // Erase X from the set S.Remove(X); // Increment ans, i.e. the number of operations // performed ans++; } // return answer return ans; } static public void Main() { // Code int N = 3; int [] A = { 2, 3, 6 }; long answer = totalOperations(N, A); // Function Call Console.WriteLine(answer); } } // This code is contributed by karthik. |
Javascript
// javascript code for the above approach // Function to find the number of // operations such that size of the // array becomes 1 function totalOperations(N, A) { // Declaring a set let S = new Set(); // Inserting all the elements of // array into the set for (let i = 0; i < N; i++) { S.add(A[i]); } // Initializing ans with 0 to store // the total operations let ans = 0; // Perform the operation, till size // of the set becomes 1 while (S.size > 1) { // Find the smallest and largest // elements of the array. i.e // first and last element of // the set let End = [...S].pop(); let Start = [...S][0]; let X = End; let Y = Start; // Calculate Z, i.e. X%Y let Z = X % Y; // If Z is non-zero, insert it // into the set if (Z) { S.add(Z); } // Erase X from the set S. delete (X); // Increment ans, i.e. the number // of operations performed ans++; } // return answer return ans; } // Driver code let N = 3; let A = [2, 3, 6]; let answer = totalOperations(N, A); // Function Call console.log(answer); // This code is contributed by shivamgupta310570 |
3
Time Complexity: O(M+N*logN), where M is the number of operations performed
Auxiliary Space : O(N)