Dados dos enteros X e Y , la tarea es encontrar e imprimir los números que dividen X e Y para producir el mismo resto.
Ejemplos:
Entrada: X = 1, Y = 5
Salida: 1, 2, 4
Explicación:
Sea el número M. Puede ser cualquier valor en el rango [1, 5]:
Si M = 1, 1 % 1 = 0 y 5 % 1 = 0
Si M = 2, 1 % 2 = 1 y 5 % 2 = 1
Si M = 3, 1 % 3 = 1 y 5 % 3 = 2
Si M = 4, 1 % 4 = 1 y 5 % 4 = 1
Si M = 5, 1 % 5 = 1 y 5 % 5 = 0
Por lo tanto, los posibles valores de M son 1, 2, 4
Entrada: X = 8, Y = 10
Salida: 1, 2
Enfoque ingenuo: El enfoque ingenuo para este problema es verificar el valor del módulo para todos los valores posibles de M en el rango [1, max(X, Y)] e imprimir el valor de M si se cumple la condición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find numbers
// that divide X and Y
// to produce the same remainder
#include <iostream>
using namespace std;
// Function to find
// the required number as M
void printModulus(int X, int Y)
{
// Finding the maximum
// value among X and Y
int n = max(X, Y);
// Loop to iterate through
// maximum value among X and Y.
for (int i = 1; i <= n; i++) {
// If the condition satisfies, then
// print the value of M
if (X % i == Y % i)
cout << i << " ";
}
}
// Driver code
int main()
{
int X, Y;
X = 10;
Y = 20;
printModulus(X, Y);
return 0;
}
Java
// Java program to find numbers
// that divide X and Y
// to produce the same remainder
class GFG{
// Function to find
// the required number as M
static void printModulus(int X, int Y)
{
// Finding the maximum
// value among X and Y
int n = Math.max(X, Y);
// Loop to iterate through
// maximum value among X and Y.
for (int i = 1; i <= n; i++) {
// If the condition satisfies, then
// print the value of M
if (X % i == Y % i)
System.out.print(i + " ");
}
}
// Driver code
public static void main(String[] args)
{
int X, Y;
X = 10;
Y = 20;
printModulus(X, Y);
}
}
// This code is contributed by Princi Singh
Python3
# Python program to find numbers # that divide X and Y # to produce the same remainder # Function to find # the required number as M def printModulus( X, Y): # Finding the maximum # value among X and Y n = max(X, Y) # Loop to iterate through # maximum value among X and Y. for i in range(1, n + 1): # If the condition satisfies, then # print the value of M if (X % i == Y % i): print(i,end=" ") # Driver code X = 10 Y = 20 printModulus(X, Y) # This code is contributed by Atul_kumar_Shrivastava
C#
// C# program to find numbers
// that divide X and Y
// to produce the same remainder
using System;
class GFG{
// Function to find
// the required number as M
static void printModulus(int X, int Y)
{
// Finding the maximum
// value among X and Y
int n = Math.Max(X, Y);
// Loop to iterate through
// maximum value among X and Y.
for (int i = 1; i <= n; i++) {
// If the condition satisfies, then
// print the value of M
if (X % i == Y % i)
Console.Write(i + " ");
}
}
// Driver code
public static void Main()
{
int X, Y;
X = 10;
Y = 20;
printModulus(X, Y);
}
}
// This code is contributed by AbhiThakur
Javascript
<script>
// Javascript program to find numbers
// that divide X and Y
// to produce the same remainder
// Function to find
// the required number as M
function printModulus(X, Y)
{
// Finding the maximum
// value among X and Y
var n = Math.max(X, Y);
// Loop to iterate through
// maximum value among X and Y.
for (var i = 1; i <= n; i++) {
// If the condition satisfies, then
// print the value of M
if (X % i == Y % i)
document.write(i+" ");
}
}
// Driver code
X = 10;
Y = 20;
printModulus(X, Y);
// This code is contributed by noob2000.
</script>
Producción:
1 2 5 10
Complejidad del tiempo: O(max(X, Y))
Espacio Auxiliar: O(1)
Enfoque Eficiente: Supongamos que Y es mayor que X por una diferencia de D .
- Entonces Y se puede expresar como
Y = X + D
and
Y % M = (X + D) % M
= (X % M) + (D % M)
- Ahora, la condición es si X % M y X % M + D % M son iguales o no .
- Aquí, dado que X % M es común en ambos lados, el valor de M es verdadero si para alguna M, D % M = 0 .
- Por lo tanto, los valores requeridos de M serán los factores de D.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find numbers
// that divide X and Y to
// produce the same remainder
#include <iostream>
using namespace std;
// Function to print all the possible values
// of M such that X % M = Y % M
void printModulus(int X, int Y)
{
// Finding the absolute difference
// of X and Y
int d = abs(X - Y);
// Iterating from 1
int i = 1;
// Loop to print all the factors of D
while (i * i <= d) {
// If i is a factor of d, then print i
if (d % i == 0) {
cout << i << " ";
// If d / i is a factor of d,
// then print d / i
if (d / i != i)
cout << d / i << " ";
}
i++;
}
}
// Driver code
int main()
{
int X = 10;
int Y = 26;
printModulus(X, Y);
return 0;
}
Java
// Java program to find numbers
// that divide X and Y to
// produce the same remainder
import java.util.*;
class GFG{
// Function to print all the possible values
// of M such that X % M = Y % M
static void printModulus(int X, int Y)
{
// Finding the absolute difference
// of X and Y
int d = Math.abs(X - Y);
// Iterating from 1
int i = 1;
// Loop to print all the factors of D
while (i * i <= d) {
// If i is a factor of d, then print i
if (d % i == 0) {
System.out.print(i+ " ");
// If d / i is a factor of d,
// then print d / i
if (d / i != i)
System.out.print(d / i+ " ");
}
i++;
}
}
// Driver code
public static void main(String[] args)
{
int X = 10;
int Y = 26;
printModulus(X, Y);
}
}
// This code is contributed by Princi Singh
Python3
# Python program to find numbers # that divide X and Y to # produce the same remainder # Function to print all the possible values # of M such that X % M = Y % M def printModulus(X, Y): # Finding the absolute difference # of X and Y d = abs(X - Y); # Iterating from 1 i = 1; # Loop to print all the factors of D while (i * i <= d): # If i is a factor of d, then pri if (d % i == 0): print(i, end=""); # If d / i is a factor of d, # then prd / i if (d // i != i): print(d // i, end=" "); i+=1; # Driver code if __name__ == '__main__': X = 10; Y = 26; printModulus(X, Y); # This code contributed by Princi Singh
C#
// C# program to find numbers
// that divide X and Y to
// produce the same remainder
using System;
public class GFG{
// Function to print all the possible values
// of M such that X % M = Y % M
static void printModulus(int X, int Y)
{
// Finding the absolute difference
// of X and Y
int d = Math.Abs(X - Y);
// Iterating from 1
int i = 1;
// Loop to print all the factors of D
while (i * i <= d) {
// If i is a factor of d, then print i
if (d % i == 0) {
Console.Write(i+ " ");
// If d / i is a factor of d,
// then print d / i
if (d / i != i)
Console.Write(d / i+ " ");
}
i++;
}
}
// Driver code
public static void Main(String[] args)
{
int X = 10;
int Y = 26;
printModulus(X, Y);
}
}
// This code contributed by Princi Singh
Javascript
<script>
// Javascript program to find numbers
// that divide X and Y to
// produce the same remainder
// Function to print all the possible values
// of M such that X % M = Y % M
function printModulus(X, Y)
{
// Finding the absolute difference
// of X and Y
var d = Math.abs(X - Y);
// Iterating from 1
var i = 1;
// Loop to print all the factors of D
while (i * i <= d) {
// If i is a factor of d, then print i
if (d % i == 0) {
document.write(i + " ");
// If d / i is a factor of d,
// then print d / i
if (d / i != i)
document.write(parseInt(d / i) + " ");
}
i++;
}
}
// Driver code
var X = 10;
var Y = 26;
printModulus(X, Y);
// This code is contributed by rrrtnx.
</script>
Producción:
1 16 2 8 4
Análisis de complejidad temporal O(sqrt(D)) , donde D es la diferencia entre los valores X e Y.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ANKITKUMAR34 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA