Given an array A of size N (> 2). The task is to find the maximum value of A[i] / A[j]
Note: A[i] ? 0.
Examples:
Input : A[] = {1, 2, 3, 4}
Output : 4
4 / 1 = 4 is maximum possible value.Input : A[] = {3, 7, 9, 3, 11}
Output : 3
Naive Approach: A naive approach is to run nested loops and find the maximum possible answer.
Time complexity : O(N2).
Efficient Approach: An efficient approach is to find maximum and minimum element in the array and print maximum / minimum
Proof:
Lets take an array A[] = {a, b, c, d} where a < b < c < d .
Now :
(b / a) < ( c / a ) < (d / a) (since b < c < d, and denominator is constant )
and since a is minimum, therefore
d / a is maximum
Below is the implementation of the above approach:
C++
// CPP program to maximum value of // division of two numbers in an array#include <bits/stdc++.h>using namespace std;// Function to maximum value of // division of two numbers in an arrayint Division(int a[], int n){ int maxi = INT_MIN, mini = INT_MAX; // Traverse through the array for (int i = 0; i < n; i++) { maxi = max(a[i], maxi); mini = min(a[i], mini); } // Return the required answer return maxi / mini;}// Driver codeint main() { int a[] = {3, 7, 9, 3, 11}; int n = sizeof(a) / sizeof(a[0]); cout << Division(a, n); return 0;} |
Java
// Java program to maximum value of // division of two numbers in an arrayimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to maximum value of // division of two numbers in an arraystatic int Division(int a[], int n){ int maxi = Integer.MIN_VALUE, mini = Integer.MAX_VALUE; // Traverse through the array for (int i = 0; i < n; i++) { maxi = Math.max(a[i], maxi); mini = Math.min(a[i], mini); } // Return the required answer return maxi / mini;}// Driver codepublic static void main (String[] args) throws java.lang.Exception{ int a[] = {3, 7, 9, 3, 11}; int n = a.length; System.out.print(Division(a, n));}}// This code is contributed by Nidhiva |
Python3
# Python3 program to maximum value of# division of two numbers in an array# Function to maximum value of# division of two numbers in an arraydef Division(a, n): maxi = -10**9 mini = 10**9 # Traverse through the array for i in a: maxi = max(i, maxi) mini = min(i, mini) # Return the required answer return maxi // mini# Driver codea = [3, 7, 9, 3, 11]n = len(a)print(Division(a, n))# This code is contributed by Mohit Kumar |
C#
// C# program to maximum value of // division of two numbers in an arrayusing System; class GFG{// Function to maximum value of // division of two numbers in an arraystatic int Division(int []a, int n){ int maxi = int.MinValue, mini = int.MaxValue; // Traverse through the array for (int i = 0; i < n; i++) { maxi = Math.Max(a[i], maxi); mini = Math.Min(a[i], mini); } // Return the required answer return maxi / mini;}// Driver codepublic static void Main (String[] args){ int []a = {3, 7, 9, 3, 11}; int n = a.Length; Console.WriteLine(Division(a, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to maximum value of // division of two numbers in an array// Function to maximum value of // division of two numbers in an arrayfunction Division(a, n){ let maxi = Number.MIN_VALUE, mini = Number.MAX_VALUE; // Traverse through the array for (let i = 0; i < n; i++) { maxi = Math.max(a[i], maxi); mini = Math.min(a[i], mini); } // Return the required answer return parseInt(maxi / mini);}// Driver code let a = [3, 7, 9, 3, 11]; let n = a.length; document.write(Division(a, n));</script> |
Output :
3
Time complexity : O(N), since the loop runs only once from 0 to (n – 1).
Auxiliary space : O(1), since no extra space has been taken.
Note: Above solution works only for positive integers
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
