Dados cuatro números positivos A, B, C, D , tales que A y B son el primer término y la diferencia común de la primera sucesión aritmética respectivamente, mientras que C y D representan lo mismo para la segunda sucesión aritmética respectivamente como se muestra a continuación:
Primera Secuencia Aritmética: A, A + B, A + 2B, A + 3B, …….
Segunda Secuencia Aritmética: C, C+ D, C+ 2D, C+ 3D, …….
La tarea es encontrar el elemento menos común de las secuencias AP anteriores. Si no existe tal número, imprima -1 .
Ejemplos:
Entrada: A = 2, B = 20, C = 19, D = 9
Salida: 82
Explicación:
Secuencia 1: {2, 2 + 20, 2 + 2(20), 2 + 3(20), 2 + 4( 20), …..} = {2, 22, 42, 62, 82 , …..}
Secuencia 2: {19, 19 + 9, 19 + 2(9), 19 + 3(9), 19 + 4 (9), 19 + 5(9), 19 + 6(9), 19 + 7(9) …..} = {19, 28, 37, 46, 55, 64, 73, 82 , …..}
Por lo tanto, 82 es el elemento común más pequeño.
Entrada: A = 2, B = 18, C = 19, D = 9
Salida: -1
Acercarse:
Dado que cualquier término de las dos sucesiones dadas se puede expresar como A + x*B y C+ y*D , por lo tanto, para resolver el problema, necesitamos encontrar los valores más pequeños de x e y para los cuales los dos términos son iguales.
Siga los pasos a continuación para resolver el problema:
- Para encontrar el valor común más pequeño en ambas secuencias AP , la idea es encontrar los valores enteros más pequeños de x e y que satisfagan la siguiente ecuación:
A + x*B = C+ y*D
=> La ecuación anterior se puede reorganizar como
x*B = C – A + y*D
=> La ecuación anterior se puede reorganizar aún más como
x = (C – A + y*D) / B
- Compruebe si existe algún valor entero y tal que (C – A + y*D) % B sea 0 o no. Si existe, entonces el número más pequeño es (C+ y*D) .
- Comprueba si (C+ y*D) es la respuesta o no, donde y estará en un rango (0, B) porque de i = B, B+1, …. los valores restantes se repetirán.
- Si no se obtiene dicho número de los pasos anteriores, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest element
// common in both the subsequences
long smallestCommon(long a, long b,
long c, long d)
{
// If a is equal to c
if (a == c)
return a;
// If a exceeds c
if (a > c) {
swap(a, c);
swap(b, d);
}
long first_term_diff = (c - a);
long possible_y;
// Check for the satisfying
// equation
for (possible_y = 0; possible_y < b; possible_y++) {
// Least value of possible_y
// satisfying the given equation
// will yield true in the below if
// and break the loop
if ((first_term_diff % b
+ possible_y * d)
% b
== 0) {
break;
}
}
// If the value of possible_y
// satisfying the given equation
// lies in range [0, b]
if (possible_y != b) {
return c + possible_y * d;
}
// If no value of possible_y
// satisfies the given equation
return -1;
}
// Driver Code
int main()
{
long A = 2, B = 20, C = 19, D = 9;
cout << smallestCommon(A, B, C, D);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the smallest element
// common in both the subsequences
static int smallestCommon(int a, int b,
int c, int d)
{
// If a is equal to c
if (a == c)
return a;
// If a exceeds c
if (a > c)
{
swap(a, c);
swap(b, d);
}
int first_term_diff = (c - a);
int possible_y;
// Check for the satisfying
// equation
for (possible_y = 0;
possible_y < b; possible_y++)
{
// Least value of possible_y
// satisfying the given equation
// will yield true in the below if
// and break the loop
if ((first_term_diff % b +
possible_y * d) % b == 0)
{
break;
}
}
// If the value of possible_y
// satisfying the given equation
// lies in range [0, b]
if (possible_y != b)
{
return c + possible_y * d;
}
// If no value of possible_y
// satisfies the given equation
return -1;
}
static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
// Driver Code
public static void main(String[] args)
{
int A = 2, B = 20, C = 19, D = 9;
System.out.print(smallestCommon(A, B, C, D));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to implement # the above approach # Function to find the smallest element # common in both the subsequences def smallestCommon(a, b, c, d): # If a is equal to c if (a == c): return a; # If a exceeds c if (a > c): swap(a, c); swap(b, d); first_term_diff = (c - a); possible_y = 0; # Check for the satisfying # equation for possible_y in range(b): # Least value of possible_y # satisfying the given equation # will yield True in the below if # and break the loop if ((first_term_diff % b + possible_y * d) % b == 0): break; # If the value of possible_y # satisfying the given equation # lies in range [0, b] if (possible_y != b): return c + possible_y * d; # If no value of possible_y # satisfies the given equation return -1; def swap(x, y): temp = x; x = y; y = temp; # Driver Code if __name__ == '__main__': A = 2; B = 20; C = 19; D = 9; print(smallestCommon(A, B, C, D)); # This code is contributed by Rajput-Ji
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the smallest element
// common in both the subsequences
static int smallestCommon(int a, int b,
int c, int d)
{
// If a is equal to c
if (a == c)
return a;
// If a exceeds c
if (a > c)
{
swap(a, c);
swap(b, d);
}
int first_term_diff = (c - a);
int possible_y;
// Check for the satisfying
// equation
for (possible_y = 0;
possible_y < b; possible_y++)
{
// Least value of possible_y
// satisfying the given equation
// will yield true in the below if
// and break the loop
if ((first_term_diff % b +
possible_y * d) % b == 0)
{
break;
}
}
// If the value of possible_y
// satisfying the given equation
// lies in range [0, b]
if (possible_y != b)
{
return c + possible_y * d;
}
// If no value of possible_y
// satisfies the given equation
return -1;
}
static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
// Driver Code
public static void Main(String[] args)
{
int A = 2, B = 20, C = 19, D = 9;
Console.Write(smallestCommon(A, B, C, D));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the
// above approach
// Function to find the smallest element
// common in both the subsequences
function smallestCommon(a, b, c, d)
{
// If a is equal to c
if (a == c)
return a;
// If a exceeds c
if (a > c)
{
swap(a, c);
swap(b, d);
}
let first_term_diff = (c - a);
let possible_y;
// Check for the satisfying
// equation
for (possible_y = 0;
possible_y < b; possible_y++)
{
// Least value of possible_y
// satisfying the given equation
// will yield true in the below if
// and break the loop
if ((first_term_diff % b +
possible_y * d) % b == 0)
{
break;
}
}
// If the value of possible_y
// satisfying the given equation
// lies in range [0, b]
if (possible_y != b)
{
return c + possible_y * d;
}
// If no value of possible_y
// satisfies the given equation
return -1;
}
function swap(x, y)
{
let temp = x;
x = y;
y = temp;
}
// Driver Code
let A = 2, B = 20, C = 19, D = 9;
document.write(smallestCommon(A, B, C, D));
</script>
82
Complejidad temporal: O(B)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saideepgummadavelly y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA