Given an array A[] consisting of distinct elements, the task is to obtain the largest possible modulus value that remains after repeatedly replacing adjacent elements by their modulus, starting from the first element, for any possible permutations of the given array.
(…(( A[1] mod A[2]) mod A[3]) …. ) mod A[N])
Examples:
Input: A[] = {7, 10, 12}
Output: 7
Explanation: All possible values of the given expression across all permutations of the given array are as follows:
{7, 10, 12} = ((7 % 10) % 12) = 7
{10, 12 7} = ((10 % 12) % 7) = 3
{7, 12, 10} =((7 % 12) % 10) = 7
{10, 7, 12} = ((10 % 7) % 12) = 3
{12, 7, 10} = ((12 % 7) % 10) = 5
{12, 10, 7} = ((12 % 10) % 7) = 2
Therefore, the maximum possible value is 7.Input: A[] = {20, 30}
Output: 20
Explanation:
The maximum possible value from all the permutations of the given array is 20.
Naive Approach: The simplest approach to solve the problem is to generate all permutations of the given array and find the value of the given expression for all permutations. Finally, print the maximum value of the expression obtained.
Time Complexity: O(N * N!)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the following observations need to be made:
- For any permutation A1…..AN, the value of the expression always lies in the range [0, min(A2…..An)-1].
- Considering K to be the smallest element in the array, the value of the expression will always be K for the permutations having K as the first element.
- For all other permutations, the value of the expression will always be less than K, as shown in the examples above. Therefore, K is the maximum possible value of the expression for any permutation of the array.
- Therefore, the maximum possible value will always be equal to the smallest element of the array.
Therefore, to solve the problem, simply traverse the array and find the minimum element present in the array and print it as the required answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// of two numbersint min(int a, int b){ return (a > b) ? b : a;}// Function to find the maximum value// possible of the given expression// from all permutations of the arrayint maximumModuloValue(int A[], int n){ // Stores the minimum value // from the array int mn = INT_MAX; for (int i = 0; i < n; i++) { mn = min(A[i], mn); } // Return the answer return mn;}// Driver Codeint main(){ int A[] = { 7, 10, 12 }; int n = (sizeof(A) / (sizeof(A[0]))); cout << maximumModuloValue(A, n) << endl; return 0;} |
Java
// Java Program to implement// the above approachimport java.io.*;class GFG{ // Function to find the maximum value // possible of the given expression // from all permutations of the array static int maximumModuloValue(int A[], int n) { // Stores the minimum value // from the array int mn = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { mn = Math.min(A[i], mn); } // Return the answer return mn; } // Driver Code public static void main(String[] args) { int A[] = {7, 10, 12}; int n = A.length; System.out.println(maximumModuloValue(A, n)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to implement# the above approachimport sys# Function to find the maximum value # possible of the given expression# from all permutations of the arraydef maximumModuloValue(A, n): # Stores the minimum value # from the array mn = sys.maxsize for i in range(n): mn = min(A[i], mn) # Return the answer return mn# Driver Code# Given array arr[]A = [ 7, 10, 12 ]n = len(A)# Function callprint(maximumModuloValue(A, n))# This code is contributed by Shivam Singh |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to find the maximum value // possible of the given expression // from all permutations of the array static int maximumModuloValue(int []A, int n) { // Stores the minimum value // from the array int mn = int.MaxValue; for (int i = 0; i < n; i++) { mn = Math.Min(A[i], mn); } // Return the answer return mn; } // Driver Code public static void Main(String[] args) { int []A = {7, 10, 12}; int n = A.Length; Console.WriteLine(maximumModuloValue(A, n)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// javascript Program to implement// the above approach // Function to find the maximum value // possible of the given expression // from all permutations of the array function maximumModuloValue(A , n) { // Stores the minimum value // from the array var mn = Number.MAX_VALUE; for (i = 0; i < n; i++) { mn = Math.min(A[i], mn); } // Return the answer return mn; } // Driver Code var A = [ 7, 10, 12 ]; var n = A.length; document.write(maximumModuloValue(A, n));// This code contributed by umadevi9616 </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 2 in python:
Approach:
We can generate all possible permutations of the array and then calculate the value of the expression for each permutation. Finally, we can return the maximum value among all these values.
- Import the itertools module to generate all permutations of the array.
- Define the maximize_modulus function that takes an array arr as input.
- Initialize max_value to negative infinity as the initial maximum value.
- Use a for loop to generate all permutations of the array using itertools.permutations.
- For each permutation, initialize value to the first element of the permutation.
- Use another for loop to calculate the modulus of value with all other elements in the permutation.
- Update value to the modulus for each iteration of the loop.
- If value is greater than the current maximum value max_value, update max_value to value.
- After all permutations have been evaluated, return max_value.
Python3
import itertoolsdef maximize_modulus(arr): max_value = float('-inf') for perm in itertools.permutations(arr): value = perm[0] for i in range(1, len(perm)): value = value % perm[i] if value > max_value: max_value = value return max_value# Test with the given inputsarr1 = [7, 10, 12]arr2 = [20, 30]print(maximize_modulus(arr1)) # Output: 7print(maximize_modulus(arr2)) # Output: 20 |
7 20
The time complexity of this approach is O(n!), where n is the length of the array, because we are generating all possible permutations of the array.
The space complexity is also O(n!) because we need to store all these permutations.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
