Módulo máximo de todos los pares de array donde arr[i] >= arr[j]

Dada una array de n enteros. Encuentre el valor máximo de arr[i] mod arr[j] donde arr[i] >= arr[j] y 1 <= i, j <= n 

Ejemplos: 

Input: arr[] = {3, 4, 7}
Output: 3
Explanation:
There are 3 pairs which satisfies arr[i] >= arr[j] are:-
4, 3 => 4 % 3 = 1
7, 3 => 7 % 3 = 1
7, 4 => 7 % 4 = 3
Hence Maximum value among all is 3.

Input: arr[] = {3, 7, 4, 11}
Output: 4

Input: arr[] = {4, 4, 4}
Output: 0

Un enfoque ingenuo es ejecutar dos bucles for anidados y seleccionar el máximo de todos los pares posibles después de tomar el módulo de ellos. La complejidad temporal de este enfoque será O(n ² ), que no será suficiente para valores grandes de n.

Un enfoque eficiente (cuando los elementos son de rango pequeño) es usar el método de clasificación y búsqueda binaria. En primer lugar, ordenaremos la array para que podamos aplicarle una búsqueda binaria. Dado que necesitamos maximizar el valor de arr[i] mod arr[j], iteramos a través de cada x (como x divisible por arr[j]) en el rango de 2*arr[j] a M+arr[j], donde M es el valor máximo de la secuencia. Para cada valor de x necesitamos encontrar el valor máximo de arr[i] tal que arr[i] < x. 

Al hacer esto, nos aseguraríamos de haber elegido solo aquellos valores de arr[i] que darán el valor máximo de arr[i] mod arr[j]. Después de eso, solo tenemos que repetir el proceso anterior para otros valores de arr[j] y actualizar la respuesta por el valor a[i] mod arr[j].

Por ejemplo:- 

If arr[] = {4, 6, 7, 8, 10, 12, 15} then for
first element, i.e., arr[j] = 4 we iterate
through x = {8, 12, 16}. 
Therefore for each value of x, a[i] will be:-
x = 8, arr[i] = 7 (7 < 8)
       ans = 7 mod 4 = 3 
x = 12, arr[i] = 10 (10 < 12)
       ans = 10 mod 4 = 2 (Since 2 < 3, 
                                No update)
x = 16, arr[i] = 15 (15 < 16)
       ans  = 15 mod 4 = 3 (Since 3 == 3,  
                        No need to update)

Implementación:

// C++ program to find Maximum modulo value
#include <bits/stdc++.h>
using namespace std;
 
int maxModValue(int arr[], int n)
{
    int ans = 0;
    // Sort the array[] by using inbuilt sort function
    sort(arr, arr + n);
 
    for (int j = n - 2; j >= 0; --j) {
        // Break loop if answer is greater or equals to
        // the arr[j] as any number modulo with arr[j]
        // can only give maximum value up-to arr[j]-1
        if (ans >= arr[j])
            break;
 
        // If both elements are same then skip the next
        // loop as it would be worthless to repeat the
        // rest process for same value
        if (arr[j] == arr[j + 1])
            continue;
 
        for (int i = 2 * arr[j]; i <= arr[n - 1] + arr[j]; i += arr[j]) {
            // Fetch the index which is greater than or
            // equals to arr[i] by using binary search
            // inbuilt lower_bound() function of C++
            int ind = lower_bound(arr, arr + n, i) - arr;
 
            // Update the answer
            ans = max(ans, arr[ind - 1] % arr[j]);
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 5, 9, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxModValue(arr, n);
}

// Java program to find Maximum modulo value
 
import java.util.Arrays;
 
class Test {
    static int maxModValue(int arr[], int n)
    {
        int ans = 0;
 
        // Sort the array[] by using inbuilt sort function
        Arrays.sort(arr);
 
        for (int j = n - 2; j >= 0; --j) {
            // Break loop if answer is greater or equals to
            // the arr[j] as any number modulo with arr[j]
            // can only give maximum value up-to arr[j]-1
            if (ans >= arr[j])
                break;
 
            // If both elements are same then skip the next
            // loop as it would be worthless to repeat the
            // rest process for same value
            if (arr[j] == arr[j + 1])
                continue;
 
            for (int i = 2 * arr[j]; i <= arr[n - 1] + arr[j]; i += arr[j]) {
                // Fetch the index which is greater than or
                // equals to arr[i] by using binary search
 
                int ind = Arrays.binarySearch(arr, i);
 
                if (ind < 0)
                    ind = Math.abs(ind + 1);
 
                else {
                    while (arr[ind] == i) {
                        ind--;
 
                        if (ind == 0) {
                            ind = -1;
                            break;
                        }
                    }
                    ind++;
                }
 
                // Update the answer
                ans = Math.max(ans, arr[ind - 1] % arr[j]);
            }
        }
        return ans;
    }
 
    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 3, 4, 5, 9, 11 };
        System.out.println(maxModValue(arr, arr.length));
    }
}

# Python3 program to find Maximum modulo value
 
def maxModValue(arr, n):
 
    ans = 0
     
    # Sort the array[] by using inbuilt
    # sort function
    arr = sorted(arr)
 
    for j in range(n - 2, -1, -1):
         
        # Break loop if answer is greater or equals to
        # the arr[j] as any number modulo with arr[j]
        # can only give maximum value up-to arr[j]-1
        if (ans >= arr[j]):
            break
 
        # If both elements are same then skip the next
        # loop as it would be worthless to repeat the
        # rest process for same value
        if (arr[j] == arr[j + 1]) :
            continue
        i = 2 * arr[j]
        while(i <= arr[n - 1] + arr[j]):
             
            # Fetch the index which is greater than or
            # equals to arr[i] by using binary search
            # inbuilt lower_bound() function of C++
            ind = 0
            for k in arr:
                if k >= i:
                    ind = arr.index(k)
 
            # Update the answer
            ans = max(ans, arr[ind - 1] % arr[j])
            i += arr[j]
 
    return ans
 
# Driver Code
arr = [3, 4, 5, 9, 11 ]
n = 5
print(maxModValue(arr, n))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# program to find Maximum modulo value
using System;
 
public class GFG {
     
    static int maxModValue(int[] arr, int n)
    {
         
        int ans = 0;
 
        // Sort the array[] by using inbuilt
        // sort function
        Array.Sort(arr);
 
        for (int j = n - 2; j >= 0; --j)
        {
             
            // Break loop if answer is greater
            // or equals to the arr[j] as any
            // number modulo with arr[j] can
            // only give maximum value up-to
            // arr[j]-1
            if (ans >= arr[j])
                break;
 
            // If both elements are same then
            // skip the next loop as it would
            // be worthless to repeat the
            // rest process for same value
            if (arr[j] == arr[j + 1])
                continue;
 
            for (int i = 2 * arr[j];
                      i <= arr[n - 1] + arr[j];
                                   i += arr[j])
            {
                 
                // Fetch the index which is
                // greater than or equals to
                // arr[i] by using binary search
 
                int ind = Array.BinarySearch(arr, i);
 
                if (ind < 0)
                    ind = Math.Abs(ind + 1);
 
                else {
                    while (arr[ind] == i) {
                        ind--;
 
                        if (ind == 0) {
                            ind = -1;
                            break;
                        }
                    }
                    ind++;
                }
 
                // Update the answer
                ans = Math.Max(ans, arr[ind - 1]
                                       % arr[j]);
            }
        }
         
        return ans;
    }
 
    // Driver method
    public static void Main()
    {
         
        int[] arr = { 3, 4, 5, 9, 11 };
         
        Console.WriteLine(
                 maxModValue(arr, arr.Length));
    }
}
 
// This code is contributed by Sam007.

<script>
 
// JavaScript program to find Maximum modulo value
 
 
function maxModValue(arr, n) {
    let ans = 0;
 
    // Sort the array[] by using inbuilt sort function
    arr.sort((a, b) => a - b);
 
    for (let j = n - 2; j >= 0; --j) {
        // Break loop if answer is greater or equals to
        // the arr[j] as any number modulo with arr[j]
        // can only give maximum value up-to arr[j]-1
        if (ans >= arr[j])
            break;
 
        // If both elements are same then skip the next
        // loop as it would be worthless to repeat the
        // rest process for same value
        if (arr[j] == arr[j + 1])
            continue;
 
        for (let i = 2 * arr[j]; i <= arr[n - 1] + arr[j];
        i += arr[j])
        {
            // Fetch the index which is greater than or
            // equals to arr[i] by using binary search
 
            let ind = arr.indexOf(i);
 
            if (ind < 0)
                ind = Math.abs(ind) + 1;
 
            else {
                while (arr[ind] == i) {
                    ind--;
 
                    if (ind == 0) {
                        ind = -1;
                        break;
                    }
                }
                ind++;
            }
 
            // Update the answer
            ans = Math.max(ans, arr[ind - 1] % arr[j]);
        }
    }
    return ans;
}
 
// Driver method
 
let arr = [3, 4, 5, 9, 11];
document.write(maxModValue(arr, arr.length));
 
</script>

4

Complejidad de tiempo: O(nlog(n) + Mlog(M)) donde n es el número total de elementos y M es el valor máximo de todos los elementos. 
Espacio auxiliar: O(1)

Este blog es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.