Given an array arr[] of positive integers of size N, the task is to find the minimum possible size of the array that can be obtained by replacing any two adjacent positive elements with their modulo i.e., (arr[i]%arr[i+1] or arr[i+1]%arr[i]).
Examples:
Input: arr[] = {3, 4, 5, 2, 1}
Output: 1
Explanation: The following series of operations leads to a minimum size of the array under given conditions.
Select i = 0 and i+1. Replace them with 3%4. Updated arr[] = {3, 5, 2, 1}
Select i = 0 and i+1. Replace them with 3%5. Updated arr[] = {3, 2, 1}
Select i = 1 and i+1. Replace them with 1%2. Updated arr[] = {3, 1}
Select i = 1 and i+1. Replace them with 1%3. Updated arr[] = {1}Input: arr[] = {2, 2, 2, 2}
Output: 2
Explanation: The following series of operations leads to a minimum size of the array under given conditions.
Select i = 0 and i+1. Replace them 2%2. Updated arr[] = {0, 2, 2}
Select i = 1 and i+1. Replace them 2%2. Updated arr[] = {0, 0}
Since there are no more adjacent positive integers left in the array we cannot perform the operation. So the final array will have no less than 2 elements.
Approach: The problem can be solved based on the following idea:
If two adjacent elements in the array are unequal then we can always make their modulo to be equal to the smaller number (a%b = a where a is smaller than b). Therefore, we can say that the smallest element in the array will remain at last after all the operations are done.
Therefore, we can say the count of the number of occurrences of the smallest element of the array is the required answer.
Follow the below steps to implement the idea:
- Initialize the cnt = 0, to store the frequency of the minimum element.
- Iterate over the array arr[], and keep on checking the count of minimum element.
- If the length of array arr[] is 1 or 2, always return 1.
- Otherwise, return ceil(cnt / 2).
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find minimum array sizeint min_size(int arr[], int n){ // If the array has one or two positive // integers then answer will always be 1 if (n == 1 || n == 2) { return 1; } int min_ele = INT_MAX, i = 0; // Stores the number of occurrences // of the smallest element int cnt = 0; // Loop to find the minimum element and // the occurrences of it for (i = 0; i < n; i++) { // If arr[i] is smaller than min_ele if (arr[i] < min_ele) { cnt = 0; min_ele = arr[i]; } if (arr[i] == min_ele) { cnt++; } } return ceil((float)cnt / 2);}// Driver codeint main(){ // Test case 1 int arr1[] = { 5, 5, 5, 5, 4 }; int N = sizeof(arr1) / sizeof(arr1[0]); // Function call cout << min_size(arr1, N) << endl; // Test case 2 int arr2[] = { 2, 2, 2, 2, 2, 2, 2 }; N = sizeof(arr2) / sizeof(arr2[0]); // Function call cout << min_size(arr2, N) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find minimum array size static int min_size(int[] arr, int n) { // If the array has one or two positive // integers then answer will always be 1 if (n == 1 || n == 2) { return 1; } int min_ele = Integer.MAX_VALUE, i = 0; // Stores the number of occurrences // of the smallest element int cnt = 0; // Loop to find the minimum element and // the occurrences of it for (i = 0; i < n; i++) { // If arr[i] is smaller than min_ele if (arr[i] < min_ele) { cnt = 0; min_ele = arr[i]; } if (arr[i] == min_ele) { cnt++; } } return (int)Math.ceil((float)cnt / 2); } public static void main(String[] args) { // Test case 1 int[] arr1 = { 5, 5, 5, 5, 4 }; int N = arr1.length; // Function call System.out.println(min_size(arr1, N)); // Test case 2 int[] arr2 = { 2, 2, 2, 2, 2, 2, 2 }; N = arr2.length; // Function call System.out.println(min_size(arr2, N)); }}// This code is contributed by lokeshmvs21. |
Python3
# python implementationimport mathimport sysdef min_size(arr, n): # If the array has one or two positive # integers then answer will always be 1 if n == 1 or n == 2: return 1 min_ele = sys.maxsize cnt = 0 for i in range(n): # If arr[i] is smaller than min_ele if arr[i] < min_ele: cnt = 0 min_ele = arr[i] if arr[i] == min_ele: cnt += 1 return math.ceil(cnt / 2)# Test case 1arr1 = [5, 5, 5, 5, 4]N = len(arr1)# Function callprint(min_size(arr1, N))# Test case 2arr2 = [2, 2, 2, 2, 2, 2, 2]N = len(arr2)# Function callprint(min_size(arr2, N))# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find minimum array size static int min_size(int[] arr, int n) { // If the array has one or two positive // integers then answer will always be 1 if (n == 1 || n == 2) { return 1; } int min_ele = int.MaxValue, i = 0; // Stores the number of occurrences // of the smallest element int cnt = 0; // Loop to find the minimum element and // the occurrences of it for (i = 0; i < n; i++) { // If arr[i] is smaller than min_ele if (arr[i] < min_ele) { cnt = 0; min_ele = arr[i]; } if (arr[i] == min_ele) { cnt++; } } return (int)Math.Ceiling((double)cnt / 2); } static public void Main() { // Code // Test case 1 int[] arr1 = { 5, 5, 5, 5, 4 }; int N = arr1.Length; // Function call Console.WriteLine(min_size(arr1, N)); // Test case 2 int[] arr2 = { 2, 2, 2, 2, 2, 2, 2 }; N = arr2.Length; // Function call Console.WriteLine(min_size(arr2, N)); }}// This code is contributed by lokesh. |
Javascript
// JavaScript code to implement the approach// Function to find minimum array sizefunction min_size(arr, n){ // If the array has one or two positive // integers then answer will always be 1 if (n == 1 || n == 2) { return 1; } let min_ele = 1e9, i = 0; // Stores the number of occurrences // of the smallest element let cnt = 0; // Loop to find the minimum element and // the occurrences of it for (i = 0; i < n; i++) { // If arr[i] is smaller than min_ele if (arr[i] < min_ele) { cnt = 0; min_ele = arr[i]; } if (arr[i] == min_ele) { cnt++; } } return Math.ceil(parseFloat(cnt) / 2);}// Driver code // Test case 1 let arr1 = [ 5, 5, 5, 5, 4 ]; let N = arr1.length; // Function call console.log( min_size(arr1, N)); // Test case 2 let arr2 = [2, 2, 2, 2, 2, 2, 2 ]; N = arr2.length; // Function call console.log( min_size(arr2, N));// This code is contributed by poojaagarwal2. |
PHP
<?php // Function to find minimum array size function min_size($arr, $n){ // If the array has one or two positive // integers then answer will always be 1 if($n == 1 || $n == 2){ return 1; } $min_ele = 1e9; $cnt = 0; // Stores the number of occurrences // of the smallest element $cnt = 0; // Loop to find the minimum element and // the occurrences of it for($i = 0; $i < $n; $i++){ // If arr[i] is smaller than min_ele if($arr[$i] < $min_ele){ $cnt = 0; $min_ele = $arr[$i]; } if($arr[$i] == $min_ele){ $cnt++; } } return ceil((float)$cnt/2); } // Driver Code // Test Case 1 $array1 = [5,5,5,5,4]; $n1 = 5; // Function Call $ans1 = min_size($array1, $n1); print($ans1."\n"); // Test Case 2 $array2 = [2,2,2,2,2,2,2]; $n2 = 7; // Function Call $ans2 = min_size($array2, $n2); print($ans2); // This code has been contributed by aditya06012001?> |
1 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
