Given an array A[] consisting of N integers, the task is to find the maximum possible value of K, such that K * |i – j| <= min(Ai, Aj), where (0 ? i < j < N).
Given expression, k * |i – j| <= min(Ai, Aj) can also be written as k = floor( min(Ai, Aj) / |i – j| )
Examples:
Input: N = 5, A[ ] = {80, 10, 12, 15, 90}
Output: 20
Explanation:
For i = 0 and j = 4, the maximum possible value of K can be obtained.
Maximum k = min(A[0], A[4]) / |0 – 4| = min(80, 90) / |-4| = 80/4 = 20Input: N = 5, A[ ] = {10, 5, 12, 15, 8}
Output: 12
Explanation:
For i = 2 and j = 3, the maximum possible value of K can be obtained.
Maximum k = min(A[2], A[3]) / |2 – 3| = min(12, 15) / |-1| = 12/1 = 12
Naive Approach:
The simplest approach to solve this problem is to generate all possible pairs from the given array, and for each pair, find the value of K and keep updating the maximum K obtained. Finally, print the maximum value of K obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, use Two Pointers technique. Follow the steps given below:
- Initialize three variables i, j and k. Initially set i = 0 and k = 0.
- Iterate over the array, starting from j = 1 up to j = N-1.
- Now, for each pair of A[i] and A[j], find min(A[i], A[j]) / ( j – i ). If it is greater than K, then update K.
- If A[ j ] >= A[i] / ( j – i ), then update pointer i to j, to make sure that among all element up to i, A[i] will result in maximum K with all upcoming A[j]
- Finally, print the maximum value of K after the array is traversed completely.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function returns maximum// possible value of kint solve(int A[], int N){ // Pointer i make sure that // A[i] will result in max k int i = 0; // Stores maximum possible k int k = 0; for (int j = 1; j < N; j++) { // Possible value of k for // current pair (A[i] and A[j]) int tempK = min(A[i], A[j]) / (j - i); // If current value exceeds k if (tempK > k) { // Update the value of k k = tempK; } // Update pointer i if (A[j] >= A[i] / (j - i)) i = j; } // Return the maxm possible k return k;}// Driver Codeint main(){ int A[] = { 10, 5, 12, 15, 8 }; int N = sizeof(A) / sizeof(A[0]); cout << solve(A, N); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function returns maximum// possible value of kstatic int solve(int A[], int N){ // Pointer i make sure that // A[i] will result in max k int i = 0; // Stores maximum possible k int k = 0; for(int j = 1; j < N; j++) { // Possible value of k for // current pair (A[i] and A[j]) int tempK = Math.min(A[i], A[j]) / (j - i); // If current value exceeds k if (tempK > k) { // Update the value of k k = tempK; } // Update pointer i if (A[j] >= A[i] / (j - i)) i = j; } // Return the maxm possible k return k;}// Driver Codepublic static void main(String[] args){ int A[] = { 10, 5, 12, 15, 8 }; int N = A.length; System.out.println(solve(A, N));}}// This code is contributed by rutvik_56 |
Python3
# Python3 program to implement# the above approach# Function returns maximum# possible value of kdef solve(A, N): # Pointer i make sure that # A[i] will result in max k i = 0 # Stores maximum possible k k = 0 for j in range(1, N): # Possible value of k for # current pair (A[i] and A[j]) tempK = (min(A[i], A[j]) // (j - i)) # If current value exceeds k if (tempK > k): # Update the value of k k = tempK # Update pointer i if (A[j] >= A[i] // (j - i)): i = j # Return the maxm possible k return k# Driver Codeif __name__ == "__main__": A = [ 10, 5, 12, 15, 8 ] N = len(A); print(solve(A, N))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function returns maximum// possible value of kstatic int solve(int[] A, int N){ // Pointer i make sure that // A[i] will result in max k int i = 0; // Stores maximum possible k int k = 0; for(int j = 1; j < N; j++) { // Possible value of k for // current pair (A[i] and A[j]) int tempK = Math.Min(A[i], A[j]) / (j - i); // If current value exceeds k if (tempK > k) { // Update the value of k k = tempK; } // Update pointer i if (A[j] >= A[i] / (j - i)) i = j; } // Return the maxm possible k return k;} // Driver Codepublic static void Main(string[] args){ int[] A = { 10, 5, 12, 15, 8 }; int N = A.Length; Console.Write(solve(A, N));}} // This code is contributed by rock_cool |
Javascript
<script>// Javascript program to implement// the above approach// Function returns maximum// possible value of kfunction solve(A, N){ // Pointer i make sure that // A[i] will result in max k let i = 0; // Stores maximum possible k let k = 0; for(let j = 1; j < N; j++) { // Possible value of k for // current pair (A[i] and A[j]) let tempK = Math.min(A[i], A[j]) / (j - i); // If current value exceeds k if (tempK > k) { // Update the value of k k = tempK; } // Update pointer i if (A[j] >= A[i] / (j - i)) i = j; } // Return the maxm possible k return k;}// Driver codelet A = [ 10, 5, 12, 15, 8 ];let N = A.length;document.write(solve(A, N));// This code is contributed by divyeshrabadiya07</script> |
12
Time Complexity: O(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!
