Dada una array arr[] de N enteros positivos. La tarea es encontrar el valor máximo posible de a[i] % a[j] sobre todos los pares de i y j .
Ejemplos:
Entrada: arr[] = {4, 5, 1, 8}
Salida: 5
Si elegimos el par (5, 8), entonces 5 % 8 nos da 5
que es el máximo posible.
Entrada: arr[] = {7, 7, 8, 8, 1}
Salida: 7
Enfoque: dado que podemos elegir cualquier par, arr[i] debe ser el segundo máximo de la array y arr[j] debe ser el elemento máximo para maximizar el valor requerido. Por lo tanto, el segundo máximo sobre la array será nuestra respuesta. Si no existe ningún segundo número más grande, entonces 0 será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the second largest
// element in the array if exists, else 0
int getMaxValue(int arr[], int arr_size)
{
int i, first, second;
// There must be at least two elements
if (arr_size < 2) {
return 0;
}
// To store the maximum and the second
// maximum element from the array
first = second = INT_MIN;
for (i = 0; i < arr_size; i++) {
// If current element is greater than first
// then update both first and second
if (arr[i] > first) {
second = first;
first = arr[i];
}
// If arr[i] is in between first and
// second then update second
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
// No second maximum found
if (second == INT_MIN)
return 0;
else
return second;
}
// Driver code
int main()
{
int arr[] = { 4, 5, 1, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMaxValue(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns the second largest
// element in the array if exists, else 0
static int getMaxValue(int arr[], int arr_size)
{
int i, first, second;
// There must be at least two elements
if (arr_size < 2)
{
return 0;
}
// To store the maximum and the second
// maximum element from the array
first = second = Integer.MIN_VALUE;
for (i = 0; i < arr_size; i++)
{
// If current element is greater than first
// then update both first and second
if (arr[i] > first)
{
second = first;
first = arr[i];
}
// If arr[i] is in between first and
// second then update second
else if (arr[i] > second && arr[i] != first)
{
second = arr[i];
}
}
// No second maximum found
if (second == Integer.MIN_VALUE)
{
return 0;
}
else
{
return second;
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = {4, 5, 1, 8};
int n = arr.length;
System.out.println(getMaxValue(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
import sys # Python 3 implementation of the approach # Function that returns the second largest # element in the array if exists, else 0 def getMaxValue(arr,arr_size): # There must be at least two elements if (arr_size < 2): return 0 # To store the maximum and the second # maximum element from the array first = -sys.maxsize-1 second = -sys.maxsize-1 for i in range(arr_size): # If current element is greater than first # then update both first and second if (arr[i] > first): second = first first = arr[i] # If arr[i] is in between first and # second then update second elif (arr[i] > second and arr[i] != first): second = arr[i] # No second maximum found if (second == -sys.maxsize-1): return 0 else: return second # Driver code if __name__ == '__main__': arr = [4, 5, 1, 8] n = len(arr) print(getMaxValue(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns the second largest
// element in the array if exists, else 0
static int getMaxValue(int []arr,
int arr_size)
{
int i, first, second;
// There must be at least two elements
if (arr_size < 2)
{
return 0;
}
// To store the maximum and the second
// maximum element from the array
first = second = int.MinValue;
for (i = 0; i < arr_size; i++)
{
// If current element is greater than first
// then update both first and second
if (arr[i] > first)
{
second = first;
first = arr[i];
}
// If arr[i] is in between first and
// second then update second
else if (arr[i] > second &&
arr[i] != first)
{
second = arr[i];
}
}
// No second maximum found
if (second == int.MinValue)
{
return 0;
}
else
{
return second;
}
}
// Driver code
public static void Main()
{
int []arr = {4, 5, 1, 8};
int n = arr.Length;
Console.Write(getMaxValue(arr, n));
}
}
// This code is contributed by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function that returns the second largest
// element in the array if exists, else 0
function getMaxValue($arr, $arr_size)
{
// There must be at least two elements
if ($arr_size < 2)
{
return 0;
}
// To store the maximum and the second
// maximum element from the array
$first = $second = -(PHP_INT_MAX - 1);
for ($i = 0; $i < $arr_size; $i++)
{
// If current element is greater than first
// then update both first and second
if ($arr[$i] > $first)
{
$second = $first;
$first = $arr[$i];
}
// If arr[i] is in between first and
// second then update second
else if ($arr[$i] > $second &&
$arr[$i] != $first)
$second = $arr[$i];
}
// No second maximum found
if ($second == -(PHP_INT_MAX-1))
return 0;
else
return $second;
}
// Driver code
$arr = array(4, 5, 1, 8);
$n = count($arr);
echo getMaxValue($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns the second largest
// element in the array if exists, else 0
function getMaxValue(arr, arr_size)
{
let i, first, second;
// There must be at least two elements
if (arr_size < 2)
{
return 0;
}
// To store the maximum and the second
// maximum element from the array
first = second = Number.MIN_VALUE;
for (i = 0; i < arr_size; i++)
{
// If current element is greater than first
// then update both first and second
if (arr[i] > first)
{
second = first;
first = arr[i];
}
// If arr[i] is in between first and
// second then update second
else if (arr[i] > second && arr[i] != first)
{
second = arr[i];
}
}
// No second maximum found
if (second == Number.MIN_VALUE)
{
return 0;
}
else
{
return second;
}
}
// Driver Code
let arr = [4, 5, 1, 8];
let n = arr.length;
document.write(getMaxValue(arr, n));
</script>
Producción:
5
Complejidad de tiempo: O(n) donde n es el tamaño de la array
Espacio auxiliar: O(1)