Dados tres enteros a , b y N . Encuentra el número total de pares distintos que se pueden formar seleccionando un número entero de 1 a a y otro de 1 a b , tal que su suma sea divisible por N.
Ejemplos:
Input : a = 4, b = 4, N = 4 Output : 4 Input : a = 5, b = 13, N = 3 Output : 22
Enfoque básico: para que un par sea divisible por N , debe contener un número del rango 1 a a y otro del 1 a b.
Entonces, para esta iteración sobre números enteros del 1 al a y para cada número entero (i), hay b/N números cuya suma con i será divisible por N. También si (i%N + b%N) >= N entonces Existe 1 par más cuya suma es divisible por N.
Por ejemplo tomó a = 7, b = 6 y N = 4:
Let's check for i = 3:
- b/N = 6/4 = 1 => hay un entero de 1 a b,
cuya suma con 3 es divisible por 4, es decir (3, 1). - También i%N + b%N = 3%4 + 6%4 = 3+2 = 5 > 4,
significa que existe un entero más de 1 a b
cuya suma con 3 es divisible por 4, es decir (3, 5).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// Iterate over 1 to a to find distinct pairs
for (int i = 1; i <= a; i++) {
// For each integer from 1 to a
// b/n integers exists such that pair
// sum is divisible by n
ans += b / n;
// If (i%n +b%n ) >= n one more pair is possible
ans += (i % n + b % n) >= n ? 1 : 0;
}
// Return answer
return ans;
}
// Driver code
int main()
{
int a = 5, b = 13, n = 3;
cout << findCountOfPairs(a, b, n);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
static int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// Iterate over 1 to a to find distinct pairs
for (int i = 1; i <= a; i++)
{
// For each integer from 1 to a
// b/n integers exists such that pair
// sum is divisible by n
ans += b / n;
// If (i%n +b%n ) >= n one more pair is possible
ans += (i % n + b % n) >= n ? 1 : 0;
}
// Return answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int a = 5, b = 13, n = 3;
System.out.println(findCountOfPairs(a, b, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python implementation of above approach # Function to find the distinct pairs from # 1-a & 1-b such that their sum is divisible by n. def findCountOfPairs(a, b, n): ans = 0 for i in range(1, a + 1): # For each integer from 1 to a # b/n integers exists such that pair # / sum is divisible by n ans += b//n # If (i%n +b%n ) >= n one more pair is possible ans += 1 if (i % n + b % n) >= n else 0 return ans # Driver code a = 5; b = 13; n = 3 print(findCountOfPairs(a, b, n)) # This code is contributed by Shrikant13
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
static int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// Iterate over 1 to a to find distinct pairs
for (int i = 1; i <= a; i++)
{
// For each integer from 1 to a
// b/n integers exists such that pair
// sum is divisible by n
ans += b / n;
// If (i%n +b%n ) >= n one more pair is possible
ans += (i % n + b % n) >= n ? 1 : 0;
}
// Return answer
return ans;
}
// Driver code
static public void Main ()
{
int a = 5, b = 13, n = 3;
Console.WriteLine(findCountOfPairs(a, b, n));
}
}
// This code has been contributed by ajit.
PHP
<?php
// PHP implementation of above approach
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
function findCountOfPairs($a, $b, $n)
{
$ans = 0;
// Iterate over 1 to a to find
// distinct pairs
for ($i = 1; $i <= $a; $i++)
{
// For each integer from 1 to a
// b/n integers exists such that pair
// sum is divisible by n
$ans += (int)($b / $n);
// If (i%n +b%n ) >= n one more
// pair is possible
$ans += (($i % $n ) +
($b % $n)) >= $n ? 1 : 0;
}
// Return answer
return $ans;
}
// Driver code
$a = 5;
$b = 13;
$n = 3;
echo findCountOfPairs($a, $b, $n);
// This code is contributed by akt_mit.
?>
Javascript
<script>
// Javascript program for the above approach
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
function findCountOfPairs(a, b, n)
{
let ans = 0;
// Iterate over 1 to a to find distinct pairs
for (let i = 1; i <= a; i++)
{
// For each integer from 1 to a
// b/n integers exists such that pair
// sum is divisible by n
ans += parseInt(b / n, 10);
// If (i%n +b%n ) >= n one more pair is possible
ans += (i % n + b % n) >= n ? 1 : 0;
}
// Return answer
return ans;
}
let a = 5, b = 13, n = 3;
document.write(findCountOfPairs(a, b, n));
// This code is contributed by mukesh07.
</script>
Producción:
22
Complejidad del tiempo : O(N)
Espacio Auxiliar: O(1)
Segundo enfoque: este enfoque es un poco complicado. Aquí encontramos cuánto par para un múltiplo de N.
Primero: – Mantenga (a<b), si no, haga usando swap.
Segundo:- Inicie un bucle for desde el múltiplo más bajo de N y recorra el múltiplo.
- Ahora el elemento más pequeño (a) es mayor o igual que el múltiplo actual, luego agregamos ((Current_Multiple) – 1) par a la ans.
- Ahora a es menor Pero b es mayor o igual de actual múltiplo que sumamos a a la ans.
- Ahora, si a y b son más pequeños que contamos el par restante para agregar a – (current_multiple – b) + 1.
- Rompe el bucle.
A continuación se muestra la implementación de la lógica anterior.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
int findCountOfPairs(int a, int b, int n)
{
if (a > b)
{
// if first element is bigger than swap
swap(a, b);
}
int temp = 1, count = 0;
// count is store the number of pair.
for (int i = n; temp > 0; i += n)
{
// we use temp for breaking a loop.
if (a >= i)
{
// count when a is greater.
temp = i - 1;
}
else if (b >= i)
{
// Count when a is smaller but
// b is greater
temp = a;
}
else if (i > b)
{
// Count when a and b both are smaller
temp = a - (i - b) + 1;
}
if (temp > 0) //breaking condition
{
// For storing The pair in count.
count += temp;
}
}
// return the number of pairs.
return count;
}
// Driver code
int main()
{
int a = 5, b = 13, n = 3;
cout << findCountOfPairs(a, b, n);
return 0;
}
// contribute by Vivek Javiya
Java
// Java implementation of
// the above approach
class GFG{
// Function to find the
// distinct pairs from
// 1-a & 1-b such that
// their sum is divisible by n.
public static int findCountOfPairs(int a,
int b,
int n)
{
if (a > b)
{
// if first element is
// bigger than swap
int temp = a;
a = b;
b = temp;
}
int temp = 1, count = 0;
// count is store the
// number of pair.
for (int i = n; temp > 0; i += n)
{
// we use temp for
// breaking a loop.
if (a >= i)
{
// count when a
// is greater.
temp = i - 1;
}
else if (b >= i)
{
// Count when a is
// smaller but
// b is greater
temp = a;
}
else if (i > b)
{
// Count when a and b
// both are smaller
temp = a - (i - b) + 1;
}
//breaking condition
if (temp > 0)
{
// For storing The
// pair in count.
count += temp;
}
}
// return the number
// of pairs.
return count;
}
// Driver code
public static void main(String[] args)
{
int a = 5, b = 13, n = 3;
System.out.print(findCountOfPairs(a,
b, n));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python implementation of above approach # Function to find the distinct pairs from # 1-a & 1-b such that their sum is divisible by n. def findCountOfPairs(a, b, n): if(a > b): # if first element is bigger than swap a, b = b, a temp = 1 count = 0 # count is store the number of pair. i = n while(temp > 0): # we use temp for breaking a loop. if(a >= i): # count when a is greater. temp = i - 1 elif(b >= i): # Count when a is smaller but # b is greater temp = a elif(i > b): # Count when a and b both are smaller temp = a - (i - b) + 1 if(temp > 0): # breaking condition # For storing The pair in count. count += temp i += n # return the number of pairs. return count # Driver code a = 5 b = 13 n = 3 print(findCountOfPairs(a, b, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# implementation of
// the above approach
using System;
class GFG
{
// Function to find the
// distinct pairs from
// 1-a & 1-b such that
// their sum is divisible by n.
static int findCountOfPairs(int a, int b, int n)
{
if (a > b)
{
// if first element is
// bigger than swap
int temp1 = a;
a = b;
b = temp1;
}
int temp = 1, count = 0;
// count is store the
// number of pair.
for (int i = n; temp > 0; i += n)
{
// we use temp for
// breaking a loop.
if (a >= i)
{
// count when a
// is greater.
temp = i - 1;
}
else if (b >= i)
{
// Count when a is
// smaller but
// b is greater
temp = a;
}
else if (i > b)
{
// Count when a and b
// both are smaller
temp = a - (i - b) + 1;
}
// breaking condition
if (temp > 0)
{
// For storing The
// pair in count.
count += temp;
}
}
// return the number
// of pairs.
return count;
}
// Driver code
static void Main()
{
int a = 5, b = 13, n = 3;
Console.WriteLine(findCountOfPairs(a, b, n));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the
// distinct pairs from
// 1-a & 1-b such that
// their sum is divisible by n.
function findCountOfPairs(a, b, n)
{
if (a > b)
{
// if first element is
// bigger than swap
let temp1 = a;
a = b;
b = temp1;
}
let temp = 1, count = 0;
// count is store the
// number of pair.
for (let i = n; temp > 0; i += n)
{
// we use temp for
// breaking a loop.
if (a >= i)
{
// count when a
// is greater.
temp = i - 1;
}
else if (b >= i)
{
// Count when a is
// smaller but
// b is greater
temp = a;
}
else if (i > b)
{
// Count when a and b
// both are smaller
temp = a - (i - b) + 1;
}
// breaking condition
if (temp > 0)
{
// For storing The
// pair in count.
count += temp;
}
}
// return the number
// of pairs.
return count;
}
let a = 5, b = 13, n = 3;
document.write(findCountOfPairs(a, b, n));
</script>
Producción :
22
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Enfoque eficiente: para resolver el problema de manera eficiente, divídalo en cuatro partes y resuélvalo como:
- Cada entero del rango 1 a N*(a/N) tendrá exactamente b/N enteros de 1 a N*(b/N) cuya suma es divisible por N.
- Existen a/N enteros del rango 1 a N*(a/N) que pueden formar pares con b%N enteros del rango N*(b/N) a b.
- Existen a%N enteros desde el rango N*(a/N) hasta a que pueden formar pares con b/N enteros que van desde 1 hasta N*(b/N).
- Existen (a%N + b%N)/N enteros del rango N*(a/N) a a y de N*(b/N) a b que pueden formar pares cuya suma es divisible por N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// pairs from 1 to n*(a/n) and 1 to n*(b/n)
ans += n * (a / n) * (b / n);
// pairs from 1 to n*(a/n) and n*(b/n) to b
ans += (a / n) * (b % n);
// pairs from n*(a/n) to a and 1 to n*(b/n)
ans += (a % n) * (b / n);
// pairs from n*(a/n) to a and n*(b/n) to b
ans += ((a % n) + (b % n)) / n;
// Return answer
return ans;
}
// Driver code
int main()
{
int a = 5, b = 13, n = 3;
cout << findCountOfPairs(a, b, n);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
class GFG
{
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
static int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// pairs from 1 to n*(a/n) and 1 to n*(b/n)
ans += n * (a / n) * (b / n);
// pairs from 1 to n*(a/n) and n*(b/n) to b
ans += (a / n) * (b % n);
// pairs from n*(a/n) to a and 1 to n*(b/n)
ans += (a % n) * (b / n);
// pairs from n*(a/n) to a and n*(b/n) to b
ans += ((a % n) + (b % n)) / n;
// Return answer
return ans;
}
// Driver code
public static void main (String[] args)
{
int a = 5, b = 13, n = 3;
System.out.println (findCountOfPairs(a, b, n));
}
}
// This code is contributed by ajit..
Python3
# Python 3 implementation of above approach # Function to find the distinct pairs from # 1-a & 1-b such that their sum is divisible by n. def findCountOfPairs(a, b, n): ans = 0 # pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * int(a / n) * int(b / n) # pairs from 1 to n*(a/n) and n*(b/n) to b ans += int(a / n) * (b % n) # pairs from n*(a/n) to a and 1 to n*(b/n) ans += (a % n) * int(b / n) # pairs from n*(a/n) to a and n*(b/n) to b ans += int(((a % n) + (b % n)) / n); # Return answer return ans # Driver code if __name__ == '__main__': a = 5 b = 13 n = 3 print(findCountOfPairs(a, b, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
static int findCountOfPairs(int a, int b, int n)
{
int ans = 0;
// pairs from 1 to n*(a/n) and 1 to n*(b/n)
ans += n * (a / n) * (b / n);
// pairs from 1 to n*(a/n) and n*(b/n) to b
ans += (a / n) * (b % n);
// pairs from n*(a/n) to a and 1 to n*(b/n)
ans += (a % n) * (b / n);
// pairs from n*(a/n) to a and n*(b/n) to b
ans += ((a % n) + (b % n)) / n;
// Return answer
return ans;
}
// Driver code
static public void Main (){
int a = 5, b = 13, n = 3;
Console.WriteLine(findCountOfPairs(a, b, n));
}
}
// This code is contributed by @Tushil
PHP
<?php
// PHP implementation of above approach
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
function findCountOfPairs($a, $b, $n)
{
$ans = 0;
// pairs from 1 to n*(a/n) and 1 to n*(b/n)
$ans += $n * (int)($a / $n) * (int)($b / $n);
// pairs from 1 to n*(a/n) and n*(b/n) to b
$ans += (int)($a / $n) * ($b % $n);
// pairs from n*(a/n) to a and 1 to n*(b/n)
$ans += ($a % $n) * (int)($b / $n);
// pairs from n*(a/n) to a and n*(b/n) to b
$ans += (($a % $n) + (int)($b % $n)) / $n;
// Return answer
return $ans;
}
// Driver code
$a = 5;
$b = 13;
$n = 3;
echo findCountOfPairs($a, $b, $n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to find the distinct pairs from
// 1-a & 1-b such that their sum is divisible by n.
function findCountOfPairs(a, b, n)
{
let ans = 0;
// pairs from 1 to n*(a/n) and 1 to n*(b/n)
ans += n * parseInt(a / n, 10) * parseInt(b / n, 10)
// pairs from 1 to n*(a/n) and n*(b/n) to b
ans += parseInt(a / n, 10) * parseInt(b % n, 10);
// pairs from n*(a/n) to a and 1 to n*(b/n)
ans += parseInt(a % n, 10) * parseInt(b / n, 10);
// pairs from n*(a/n) to a and n*(b/n) to b
ans += parseInt(((a % n) + (b % n)) / n, 10);
// Return answer
return ans;
}
let a = 5, b = 13, n = 3;
document.write(findCountOfPairs(a, b, n));
</script>
Producción:
22
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA