Dado un entero n , la tarea es contar el número de pares (i, j) tales que ((n % i) % j) % n se maximiza donde 1 ≤ i, j ≤ n
Ejemplos:
Entrada: n = 5
Salida: 3
(3, 3), (3, 4) y (3, 5) son los únicos pares válidos.
Entrada: n = 55
Salida: 28
Enfoque ingenuo: para obtener el valor residual máximo, n debe dividirse por (n / 2) + 1 . Store max = n % ((n / 2) + 1) , ahora verifique todos los valores posibles de i y j . Si ((n % i) % j) % n = máx. , entonces actualice el conteo = conteo + 1 . Imprime el conteo al final.
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of required pairs
int countPairs(int n)
{
// Number which will give the max value
// for ((n % i) % j) % n
int num = ((n / 2) + 1);
// To store the maximum possible value of
// ((n % i) % j) % n
int max = n % num;
// To store the count of possible pairs
int count = 0;
// Check all possible pairs
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// Calculating the value of ((n % i) % j) % n
int val = ((n % i) % j) % n;
// If value is equal to maximum
if (val == max)
count++;
}
}
// Return the number of possible pairs
return count;
}
// Driver code
int main()
{
int n = 5;
cout << (countPairs(n));
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
class GFG {
// Function to return the count of required pairs
public static int countPairs(int n)
{
// Number which will give the max value
// for ((n % i) % j) % n
int num = ((n / 2) + 1);
// To store the maximum possible value of
// ((n % i) % j) % n
int max = n % num;
// To store the count of possible pairs
int count = 0;
// Check all possible pairs
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// Calculating the value of ((n % i) % j) % n
int val = ((n % i) % j) % n;
// If value is equal to maximum
if (val == max)
count++;
}
}
// Return the number of possible pairs
return count;
}
// Driver code
public static void main(String[] args)
{
int n = 5;
System.out.println(countPairs(n));
}
}
Python3
# Python3 implementation of the approach # Function to return the count of # required pairs def countPairs(n): # Number which will give the Max # value for ((n % i) % j) % n num = ((n // 2) + 1) # To store the Maximum possible value # of ((n % i) % j) % n Max = n % num # To store the count of possible pairs count = 0 # Check all possible pairs for i in range(1, n + 1): for j in range(1, n + 1): # Calculating the value of # ((n % i) % j) % n val = ((n % i) % j) % n # If value is equal to Maximum if (val == Max): count += 1 # Return the number of possible pairs return count # Driver code n = 5 print(countPairs(n)) # This code is contributed # by Mohit Kumar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the count of required pairs
static int countPairs(int n)
{
// Number which will give the max
// value for ((n % i) % j) % n
int num = ((n / 2) + 1) ;
// To store the maximum possible value
// of ((n % i) % j) % n
int max = n % num;
// To store the count of possible pairs
int count = 0;
// Check all possible pairs
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// Calculating the value of
// ((n % i) % j) % n
int val = ((n % i) % j) % n;
// If value is equal to maximum
if (val == max)
count++;
}
}
// Return the number of possible pairs
return count;
}
// Driver code
public static void Main()
{
int n = 5;
Console.WriteLine(countPairs(n));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the
// approach Function to return
// the count of required pairs
function countPairs($n)
{
// Number which will give the max
// value for ((n % i) % j) % n
$num = (($n / 2) + 1);
// To store the maximum possible
// value of ((n % i) % j) % n
$max = $n % $num;
// To store the count of possible pairs
$count = 0;
// Check all possible pairs
for ($i = 1; $i <= $n; $i++)
{
for ($j = 1; $j <= $n; $j++)
{
// Calculating the value
// of ((n % i) % j) % n
$val = (($n % $i) % $j) % $n;
// If value is equal to maximum
if ($val == $max)
$count++;
}
}
// Return the number of possible pairs
return $count;
}
// Driver code
$n = 5;
echo (countPairs($n));
// This code is contributed by ajit..
?>
Javascript
<script>
// JavaScript implementation of the above approach
// Function to return the count of required pairs
function countPairs(n)
{
// Number which will give the max
// value for ((n % i) % j) % n
let num = (parseInt(n / 2, 10) + 1) ;
// To store the maximum possible value
// of ((n % i) % j) % n
let max = n % num;
// To store the count of possible pairs
let count = 0;
// Check all possible pairs
for (let i = 1; i <= n; i++)
{
for (let j = 1; j <= n; j++)
{
// Calculating the value of
// ((n % i) % j) % n
let val = ((n % i) % j) % n;
// If value is equal to maximum
if (val == max)
count++;
}
}
// Return the number of possible pairs
return count;
}
let n = 5;
document.write(countPairs(n));
</script>
Producción:
3
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: Obtenga el valor máximo para el resto, es decir, max = n % num donde num = ((n / 2) + 1) . Ahora i debe elegirse como num para obtener el valor máximo y j puede elegirse como cualquier valor del rango [max, n] porque no necesitamos reducir el valor máximo calculado y elegir j > max no lo hará afectar el valor anterior obtenido. Entonces los pares totales serán n – max .
Este enfoque no funcionará para n = 2 . Esto se debe a que, para n = 2 , el resto máximo será 0 yn – max dará 2 pero sabemos que la respuesta es 4 . Todos los pares posibles en este caso son (1, 1) , (1, 2) , (2, 1) y (2, 2) .
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 to return the count of
// required pairs
int countPairs(int n)
{
// Special case
if (n == 2)
return 4;
// Number which will give the max value
// for ((n % i) % j) % n
int num = ((n / 2) + 1);
// To store the maximum possible value
// of ((n % i) % j) % n
int max = n % num;
// Count of possible pairs
int count = n - max;
return count;
}
// Driver code
int main()
{
int n = 5;
cout << countPairs(n);
}
// This code is contributed by Code_Mech.
Java
// Java implementation of the approach
class GFG {
// Function to return the count of required pairs
public static int countPairs(int n)
{
// Special case
if (n == 2)
return 4;
// Number which will give the max value
// for ((n % i) % j) % n
int num = ((n / 2) + 1);
// To store the maximum possible value of
// ((n % i) % j) % n
int max = n % num;
// Count of possible pairs
int count = n - max;
return count;
}
// Driver code
public static void main(String[] args)
{
int n = 5;
System.out.println(countPairs(n));
}
}
Python3
# Python3 implementation of the approach # Function to return the count of required pairs def countPairs(n): # Special case if (n == 2): return 4 # Number which will give the max value # for ((n % i) % j) % n num = ((n // 2) + 1); # To store the maximum possible value # of ((n % i) % j) % n max = n % num; # Count of possible pairs count = n - max; return count # Driver code if __name__ =="__main__" : n = 5; print(countPairs(n)); # This code is contributed by Code_Mech
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the count of required pairs
static int countPairs(int n)
{
// Special case
if (n == 2)
return 4;
// Number which will give the max value
// for ((n % i) % j) % n
int num = ((n / 2) + 1);
// To store the maximum possible value of
// ((n % i) % j) % n
int max = n % num;
// Count of possible pairs
int count = n - max;
return count;
}
// Driver code
static public void Main ()
{
int n = 5;
Console.WriteLine(countPairs(n));
}
}
// This code is contributed by Tushil..
PHP
<?php
// PHP implementation of the approach
// Function to return the count
// of required pairs
function countPairs($n)
{
// Special case
if ($n == 2)
return 4;
// Number which will give the max
// value. for ((n % i) % j) % n
$num = ((int)($n / 2) + 1);
// To store the maximum possible
// value of((n % i) % j) % n
$max = $n % $num;
// Count of possible pairs
$count = ($n - $max);
return $count;
}
// Driver code
$n = 5;
echo (countPairs($n));
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// required pairs
function countPairs(n)
{
// Special case
if (n == 2)
return 4;
// Number which will give the max value
// for ((n % i) % j) % n
let num = (parseInt(n / 2, 10) + 1);
// To store the maximum possible value
// of ((n % i) % j) % n
let max = n % num;
// Count of possible pairs
let count = n - max;
return count;
}
let n = 5;
document.write(countPairs(n));
</script>
Producción:
3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)