Dada una array arr[] , la tarea es encontrar el valor máximo de arr[i] % arr[j] para todos los pares posibles.
Ejemplos:
Entrada: arr[] = { 2, 3 }
Salida: 2
2 % 3 = 2
3 % 2 = 1
Entrada: arr[] = { 2, 2, 2, 2 }
Salida: 0
Enfoque ingenuo: ejecute dos bucles anidados y calcule el valor de arr[i] % arr[j] para cada par. Actualice la respuesta de acuerdo con el valor calculado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return maximum value of
// arr[i] % arr[j]
int computeMaxValue(const int* arr, int n)
{
int ans = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check pair (x, y) as well as
// (y, x) for maximum value
int val = max(arr[i] % arr[j],
arr[j] % arr[i]);
// Update the answer
ans = max(ans, val);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << computeMaxValue(arr, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to return maximum value of
// arr[i] % arr[j]
static int computeMaxValue(int []arr, int n)
{
int ans = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check pair (x, y) as well as
// (y, x) for maximum value
int val = Math.max(arr[i] % arr[j],
arr[j] % arr[i]);
// Update the answer
ans = Math.max(ans, val);
}
}
return ans;
}
// Driver code
public static void main(String []args)
{
int []arr = { 2, 3 };
int n = arr.length;
System.out.println(computeMaxValue(arr, n));
}
}
// This code is contributed
// by ihritik
Python3
# Python3 implementation of the above approach # Function to return maximum value of # arr[i] % arr[j] def computeMaxValue(arr, n): ans = 0 for i in range(0, n-1): for j in range( i+1, n): # Check pair (x, y) as well as # (y, x) for maximum value val = max(arr[i] % arr[j], arr[j] % arr[i]) # Update the answer ans = max(ans, val) return ans # Driver code arr = [ 2, 3 ] n = len(arr) print(computeMaxValue(arr, n)) # This code is contributed # by ihritik
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return maximum value of
// arr[i] % arr[j]
static int computeMaxValue(int []arr, int n)
{
int ans = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check pair (x, y) as well as
// (y, x) for maximum value
int val = Math.Max(arr[i] % arr[j],
arr[j] % arr[i]);
// Update the answer
ans = Math.Max(ans, val);
}
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 2, 3 };
int n = arr.Length;
Console.WriteLine(computeMaxValue(arr, n));
}
}
// This code is contributed
// by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to return maximum value of
// arr[i] % arr[j]
function computeMaxValue($arr, $n)
{
$ans = 0;
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
// Check pair (x, y) as well as
// (y, x) for maximum value
$val = max($arr[$i] % $arr[$j],
$arr[$j] % $arr[$i]);
// Update the answer
$ans = max($ans, $val);
}
}
return $ans;
}
// Driver code
$arr = array( 2, 3 );
$n = sizeof($arr);
echo computeMaxValue($arr, $n);
// This code is contributed
// by ihritik
?>
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to return maximum value of
// arr[i] % arr[j]
function computeMaxValue(arr, n)
{
let ans = 0;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
// Check pair (x, y) as well as
// (y, x) for maximum value
let val = Math.max(arr[i] % arr[j],
arr[j] % arr[i]);
// Update the answer
ans = Math.max(ans, val);
}
}
return ans;
}
let arr = [ 2, 3 ];
let n = arr.length;
document.write(computeMaxValue(arr, n));
</script>
Producción:
2
Enfoque eficiente: el valor máximo de A % B se obtendrá cuando A < B y A y B sean los máximos posibles . En otras palabras, el resultado será el segundo elemento más grande de la array, excepto en el caso en que todos los elementos de la array sean iguales (en ese caso, el resultado será 0 ).
A = segundo elemento más grande de la array.
B = elemento más grande de la array y A < B.
Valor máximo de A % B = A.
Caso de la esquina: si todos los elementos de la array son iguales, diga arr[] = {x, x, x, x} entonces el resultado será x % x = 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return maximum value of
// arr[i] % arr[j]
int computeMaxValue(const int* arr, int n)
{
bool allSame = true;
int i = 1;
while (i < n) {
// If current element is different
// from the previous element
if (arr[i] != arr[i - 1]) {
allSame = false;
break;
}
i++;
}
// If all the elements of the array are equal
if (allSame)
return 0;
// Maximum element from the array
int max = *std::max_element(arr, arr + n);
int secondMax = 0;
for (i = 0; i < n; i++) {
if (arr[i] < max && arr[i] > secondMax)
secondMax = arr[i];
}
// Return the second maximum element
// from the array
return secondMax;
}
// Driver code
int main()
{
int arr[] = { 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << computeMaxValue(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to return maximum value of
// arr[i] % arr[j]
static int computeMaxValue(int arr[], int n)
{
boolean allSame = true;
int i = 1;
while (i < n)
{
// If current element is different
// from the previous element
if (arr[i] != arr[i - 1])
{
allSame = false;
break;
}
i++;
}
// If all the elements of the
// array are equal
if (allSame)
return 0;
// Maximum element from the array
int max = -1;
for(i = 0; i < n; i++)
{
if(max < arr[i])
max = arr[i];
}
int secondMax = 0;
for (i = 0; i < n; i++)
{
if (arr[i] < max && arr[i] > secondMax)
secondMax = arr[i];
}
// Return the second maximum element
// from the array
return secondMax;
}
// Driver code
public static void main(String[] args)
{
int []arr = { 2, 3 };
int n = arr.length;
System.out.println(computeMaxValue(arr, n));
}
}
// This code is contributed
// by 29AjayKumar
Python3
# Python3 implementation of the # above approach # Function to return maximum value # of arr[i] % arr[j] def computeMaxValue(arr, n) : allSame = True; i = 1; while (i < n) : # If current element is different # from the previous element if (arr[i] != arr[i - 1]) : allSame = False break i += 1 # If all the elements of the # array are equal if (allSame) : return 0 # Maximum element from the array max_element = max(arr) secondMax = 0 for i in range(n) : if (arr[i] < max_element and arr[i] > secondMax) : secondMax = arr[i] # Return the second maximum element # from the array return secondMax # Driver code if __name__ == "__main__" : arr = [ 2, 3 ] n = len(arr) print(computeMaxValue(arr, n)) # This code is contributed by Ryuga
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return maximum value of
// arr[i] % arr[j]
static int computeMaxValue(int[] arr, int n)
{
bool allSame = true;
int i = 1;
while (i < n)
{
// If current element is different
// from the previous element
if (arr[i] != arr[i - 1])
{
allSame = false;
break;
}
i++;
}
// If all the elements of the
// array are equal
if (allSame)
return 0;
// Maximum element from the array
int max = -1;
for(i = 0; i < n; i++)
{
if(max < arr[i])
max = arr[i];
}
int secondMax = 0;
for (i = 0; i < n; i++)
{
if (arr[i] < max && arr[i] > secondMax)
secondMax = arr[i];
}
// Return the second maximum element
// from the array
return secondMax;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3 };
int n = arr.Length;
Console.Write(computeMaxValue(arr, n));
}
}
// This code is contributed by Ita_c.
PHP
<?php
// PHP implementation of the above approach
// Function to return maximum value of
// arr[i] % arr[j]
function computeMaxValue($arr, $n)
{
$allSame = true;
$i = 1;
while ($i < $n)
{
// If current element is different
// from the previous element
if ($arr[$i] != $arr[$i - 1])
{
$allSame = false;
break;
}
$i++;
}
// If all the elements of the
// array are equal
if ($allSame)
return 0;
// Maximum element from the array
$max = max($arr);
$secondMax = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] < $max &&
$arr[$i] > $secondMax)
$secondMax = $arr[$i];
}
// Return the second maximum
// element from the array
return $secondMax;
}
// Driver code
$arr = array(2, 3);
$n = sizeof($arr);
echo computeMaxValue($arr, $n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to return maximum value of
// arr[i] % arr[j]
function computeMaxValue(arr, n)
{
let allSame = true;
let i = 1;
while (i < n)
{
// If current element is different
// from the previous element
if (arr[i] != arr[i - 1])
{
allSame = false;
break;
}
i++;
}
// If all the elements of the
// array are equal
if (allSame)
return 0;
// Maximum element from the array
let max = -1;
for(i = 0; i < n; i++)
{
if(max < arr[i])
max = arr[i];
}
let secondMax = 0;
for (i = 0; i < n; i++)
{
if (arr[i] < max && arr[i] > secondMax)
secondMax = arr[i];
}
// Return the second maximum element
// from the array
return secondMax;
}
let arr = [ 2, 3 ];
let n = arr.length;
document.write(computeMaxValue(arr, n));
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por rohan23chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA