Given an array arr[] of size N, the task is to find 4 indices i, j, k, l such that 0 <= i, j, k, l < N and the value of arr[i]%arr[j] – arr[k]%arr[l] is maximum. Print the maximum difference. If it doesn’t exist, then print -1.
Examples:
Input: N=8, arr[] = {1, 2, 4, 6, 8, 3, 5, 7}
Output: 7
Explanation: Choosing elements 1, 2, 7, 8 and 2%1 – 7%8 gives the maximum result possible.Input: N=3, arr[] = {1, 50, 101}
Output: -1
Explanation: Since, there are 3 elements only so there’s no possible answer.
Naive Approach: The brute force idea would be to check all the possible combinations and then find the maximum difference.
Time Complexity: O(N4)
Auxiliary Space: O(1)
Efficient Approach: The idea is based on the observation that on sorting the array in ascending order, choose the first pair from the left-side, i.e, the minimum 2 values and the second pair from the right side, i.e, the maximum 2 values gives the answer. Further, arr[i+1]%arr[i] is always less than equal to arr[i]%arr[i+1]. So, minimize the first pair value and maximize the second pair value. Follow the steps below to solve the problem:
- If the size of the array is less than 4, then return -1.
- Sort the array arr[] in ascending order.
- Initialize the variable first as arr[1]%arr[0] and second as arr[N-2]%arr[N-1].
- After performing the above steps, print the value of second-first as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the required// maximum differencevoid maxProductDifference(vector<int>& arr){ // Base Case if (arr.size() < 4) { cout << "-1\n"; return; } // Sort the array sort(arr.begin(), arr.end()); // First pair int first = arr[1] % arr[0]; // Second pair int second = arr[arr.size() - 2] % arr[arr.size() - 1]; // Print the result cout << second - first; return;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 4, 6, 8, 3, 5, 7 }; maxProductDifference(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.Arrays;class GFG { // Function to find the required // maximum difference static void maxProductDifference(int[] arr) { // Base Case if (arr.length < 4) { System.out.println("-1"); return; } // Sort the array Arrays.sort(arr); // First pair int first = arr[1] % arr[0]; // Second pair int second = arr[arr.length - 2] % arr[arr.length - 1]; // Print the result System.out.println(second - first); return; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 4, 6, 8, 3, 5, 7 }; maxProductDifference(arr); }}// This code is contributed by Potta Lokesh |
Python3
# python program for the above approach# Function to find the required# maximum differencedef maxProductDifference(arr): # Base Case if (len(arr) < 4): print("-1") return # Sort the array arr.sort() # First pair first = arr[1] % arr[0] # Second pair second = arr[len(arr) - 2] % arr[len(arr) - 1] # Print the result print(second - first)# Driver Codeif __name__ == "__main__": arr = [1, 2, 4, 6, 8, 3, 5, 7] maxProductDifference(arr) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the required // maximum difference static void maxProductDifference(int[] arr) { // Base Case if (arr.Length < 4) { Console.WriteLine("-1"); return; } // Sort the array Array.Sort(arr); // First pair int first = arr[1] % arr[0]; // Second pair int second = arr[arr.Length - 2] % arr[arr.Length - 1]; // Print the result Console.WriteLine(second - first); return; } // Driver Code public static void Main(String[] args) { int[] arr = { 1, 2, 4, 6, 8, 3, 5, 7 }; maxProductDifference(arr); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to find the required// maximum differencefunction maxProductDifference(arr){ // Base Case if (arr.length < 4) { document.write("-1<br>"); return; } // Sort the array arr.sort(); // First pair let first = arr[1] % arr[0]; // Second pair let second = arr[arr.length - 2] % arr[arr.length - 1]; // Print the result document.write(second - first); return;}// Driver Codelet arr = [1, 2, 4, 6, 8, 3, 5, 7];maxProductDifference(arr);// This code is contributed by gfgking.</script> |
7
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
