Dado arr[] de 5 enteros que denotan los valores de X+Y, X−Y, X*Y, X%Y y ⌊X/Y⌋ en orden ordenado para dos enteros distintos de cero X e Y, la tarea es encontrar el valor de X e Y.
Nota: si no existe una solución, devuelva dos 0
Ejemplos :
Entrada : -1, 0, 4, 9, 20
Salida : X = 4, Y = 5
Explicación : Si consideramos, X + Y = 9, X – Y = -1.
Entonces X e Y son 4 y 5, lo que satisface la condición
X * Y = 20, X % Y = 4, Floor(X / Y) = 0.Entrada : -3, -1, 0, 2, 2
Salida : X = -2, Y = -1
Enfoque : el problema se puede resolver con base en la siguiente observación matemática
Si tenemos X+Y y XY podemos encontrar X e Y.
X = [(X+Y)+(XY)]/2
Y = X+YX
Para implementar la idea anterior, pruebe todos los pares posibles de valores para X+Y y XY usando backtracking . Siga los pasos a continuación para resolver el problema:
- Considere los elementos de la array como A, B, C, D, E
- Pruebe todos los pares posibles para el valor de X+Y y XY.
- Encuentre X e Y a partir de esos dos valores según la observación anterior.
- Si esos dos valores de X e Y satisfacen los otros valores, entonces regrese.
- De lo contrario, intente con otro par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to check if X and Y
// are valid or not
pair<ll, ll> isValid(ll A, ll B, ll C, ll D, ll E)
{
// a represents 2*a for now
ll a = A + B;
// 2a/2 = a that must be integer
if (ceil(float(a / 2)) != floor(float(a / 2))) {
return make_pair(0, 0);
}
else {
// Find value of a
a = a / 2;
// Find value of b
ll b = A - a;
// Edge Cases
if (a == 0 || b == 0)
return make_pair(0, 0);
else if ((a + b) > pow(10, 3)
|| (a - b) < pow(-10, 3))
return make_pair(0, 0);
// 1st Condition, C = a*b
else if ((a * b == C) && (a / b == D)
&& (a % b == E)
|| (a * b == C) && (a / b == E)
&& (a % b == D))
return make_pair(a, b);
// 2nd Condition, D = a*b
else if ((a * b == D) && (a / b == C)
&& (a % b == E)
|| (a * b == D) && (a / b == E)
&& (a % b == C))
return make_pair(a, b);
// 3rd Condition, E = a*b
else if ((a * b == E) && (a / b == C)
&& (a % b == D)
|| (a * b == E) && (a / b == D)
&& (a % b == C))
return make_pair(a, b);
// Pairs are not valid then return 0
else
return make_pair(0, 0);
}
}
// Function to find two integers X and Y
void findNum(ll* arr)
{
pair<ll, ll> p;
bool flag = 0;
for (int i = 0; i <= 4; i++) {
// Swapping for every
// X + Y combination
swap(arr[0], arr[i]);
for (int j = 1; j <= 4; j++) {
// Swapping for every
// X - Y combination
swap(arr[1], arr[j]);
// Checking for valid X and Y
p = isValid(arr[0], arr[1],
arr[2], arr[3],
arr[4]);
// If both are not -1 then
// we found X and Y
if ((p.first != 0)
&& (p.second != 0)) {
// Set Flag = true
flag = 1;
// Print the values in order
// i.e., X and Y
cout << p.first << " "
<< p.second << endl;
}
// Backtracking
swap(arr[1], arr[j]);
// X and Y are found
if (flag)
break;
}
// Backtracking
swap(arr[0], arr[i]);
// X and Y are found
if (flag)
break;
}
// If flag is 0 then X and Y
// can't be possible
if (!flag)
cout << 0 << " " << 0 << endl;
}
// Driver Code
int main()
{
int N = 5;
ll arr[N] = { -1, 0, 4, 9, 20 };
// Function call
findNum(arr);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to check if X and Y
// are valid or not
public static long[] isValid(long A, long B, long C,
long D, long E)
{
// a represents 2*a for now
long a = A + B;
// 2a/2 = a that must be integer
if (Math.ceil((a / 2.0)) != Math.floor((a / 2.0))) {
long ans[] = { 0, 0 };
return ans;
}
else {
// Find value of a
a = a / 2;
// Find value of b
long b = A - a;
long res[] = { 0, 0 };
long res1[] = { a, b };
// Edge Cases
if (a == 0 || b == 0)
return res;
else if ((a + b) > Math.pow(10, 3)
|| (a - b) < Math.pow(-10, 3))
return res;
// 1st Condition, C = a*b
else if ((a * b == C) && (a / b == D)
&& (a % b == E)
|| (a * b == C) && (a / b == E)
&& (a % b == D))
return res1;
// 2nd Condition, D = a*b
else if ((a * b == D) && (a / b == C)
&& (a % b == E)
|| (a * b == D) && (a / b == E)
&& (a % b == C))
return res1;
// 3rd Condition, E = a*b
else if ((a * b == E) && (a / b == C)
&& (a % b == D)
|| (a * b == E) && (a / b == D)
&& (a % b == C))
return res1;
// Pairs are not valid then return 0
else
return res;
}
}
// Function to find two integers X and Y
public static void findNum(long arr[])
{
long p[] = new long[2];
int flag = 0;
for (int i = 0; i <= 4; i++) {
// Swapping for every
// X + Y combination
long tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
for (int j = 1; j <= 4; j++) {
// Swapping for every
// X - Y combination
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// Checking for valid X and Y
p = isValid(arr[0], arr[1], arr[2], arr[3],
arr[4]);
// If both are not -1 then
// we found X and Y
if ((p[0] != 0) && (p[1] != 0)) {
// Set Flag = true
flag = 1;
// Print the values in order
// i.e., X and Y
System.out.println(p[0] + " " + p[1]);
}
// Backtracking
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// Backtracking
tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// If flag is 0 then X and Y
// can't be possible
if (flag == 0)
System.out.println("0 0");
}
public static void main(String[] args)
{
int N = 5;
long arr[] = { -1, 0, 4, 9, 20 };
// Function call
findNum(arr);
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python program for above approach
import math
# Function to check if X and Y
# are valid or not
def isValid(A, B, C, D, E) :
# a represents 2*a for now
a = A + B
# 2a/2 = a that must be integer
if (math.ceil((a / 2.0)) != math.floor((a / 2.0))) :
ans = [0, 0]
return ans
else :
# Find value of a
a = a // 2
# Find value of b
b = A - a
res = [ 0, 0]
res1 = [ a, b ]
# Edge Cases
if (a == 0 or b == 0) :
return res
elif ((a + b) > pow(10, 3)
or (a - b) < pow(-10, 3)) :
return res
# 1st Condition, C = a*b
elif ((a * b == C) and (a // b == D)
and (a % b == E)
or (a * b == C) and (a // b == E)
and (a % b == D)) :
return res1
# 2nd Condition, D = a*b
elif ((a * b == D) and (a // b == C)
and (a % b == E)
or (a * b == D) and (a // b == E)
and (a % b == C)) :
return res1
# 3rd Condition, E = a*b
elif ((a * b == E) and (a // b == C)
and (a % b == D)
or (a * b == E) and (a // b == D)
and (a % b == C)) :
return res1
# Pairs are not valid then return 0
else :
return res
# Function to find two integers X and Y
def findNum(arr) :
p = [0] * 2
flag = 0
for i in range(0, 5, 1) :
# Swapping for every
# X + Y combination
tmp = arr[0]
arr[0] = arr[i]
arr[i] = tmp
for j in range(1, 5, 1) :
# Swapping for every
# X - Y combination
tmp = arr[1]
arr[1] = arr[j]
arr[j] = tmp
# Checking for valid X and Y
p = isValid(arr[0], arr[1], arr[2], arr[3], arr[4])
# If both are not -1 then
# we found X and Y
if ((p[0] != 0) and (p[1] != 0)) :
# Set Flag = true
flag = 1
# Print the values in order
# i.e., X and Y
print(p[0], end = " ")
print(p[1])
# Backtracking
tmp = arr[1]
arr[1] = arr[j]
arr[j] = tmp
# X and Y are found
if (flag != 0) :
break
# Backtracking
tmp = arr[0]
arr[0] = arr[j]
arr[i] = tmp
# X and Y are found
if (flag != 0) :
break
# If flag is 0 then X and Y
# can't be possible
if (flag == 0) :
print("0 0")
# Driver code
if __name__ == "__main__":
N = 5
arr = [ -1, 0, 4, 9, 20 ]
# Function call
findNum(arr)
# This code is contributed by code_hunt.
C#
// C# code to implement the approach
using System;
public class GFG{
// Function to check if X and Y
// are valid or not
static long[] isValid(long A, long B, long C,
long D, long E)
{
// a represents 2*a for now
long a = A + B;
// 2a/2 = a that must be integer
if (Math.Ceiling((a / 2.0)) != Math.Floor((a / 2.0))) {
long[] ans = { 0, 0 };
return ans;
}
else {
// Find value of a
a = a / 2;
// Find value of b
long b = A - a;
long[] res = { 0, 0 };
long[] res1 = { a, b };
// Edge Cases
if (a == 0 || b == 0)
return res;
else if ((a + b) > Math.Pow(10, 3)
|| (a - b) < Math.Pow(-10, 3))
return res;
// 1st Condition, C = a*b
else if ((a * b == C) && (a / b == D)
&& (a % b == E)
|| (a * b == C) && (a / b == E)
&& (a % b == D))
return res1;
// 2nd Condition, D = a*b
else if ((a * b == D) && (a / b == C)
&& (a % b == E)
|| (a * b == D) && (a / b == E)
&& (a % b == C))
return res1;
// 3rd Condition, E = a*b
else if ((a * b == E) && (a / b == C)
&& (a % b == D)
|| (a * b == E) && (a / b == D)
&& (a % b == C))
return res1;
// Pairs are not valid then return 0
else
return res;
}
}
// Function to find two integers X and Y
static void findNum(long[] arr)
{
long[] p = new long[2];
int flag = 0;
for (int i = 0; i <= 4; i++) {
// Swapping for every
// X + Y combination
long tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
for (int j = 1; j <= 4; j++) {
// Swapping for every
// X - Y combination
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// Checking for valid X and Y
p = isValid(arr[0], arr[1], arr[2], arr[3],
arr[4]);
// If both are not -1 then
// we found X and Y
if ((p[0] != 0) && (p[1] != 0)) {
// Set Flag = true
flag = 1;
// Print the values in order
// i.e., X and Y
Console.WriteLine(p[0] + " " + p[1]);
}
// Backtracking
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// Backtracking
tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// If flag is 0 then X and Y
// can't be possible
if (flag == 0)
Console.WriteLine("0 0");
}
static public void Main (){
long[] arr = { -1, 0, 4, 9, 20 };
// Function call
findNum(arr);
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
// Function to check if X and Y
// are valid or not
function isValid(A, B, C, D, E)
{
// a represents 2*a for now
let a = A + B;
// 2a/2 = a that must be integer
if (Math.ceil((a / 2)) != Math.floor((a / 2))) {
let ans = [ 0, 0 ];
return ans;
}
else {
// Find value of a
a = Math.floor(a / 2);
// Find value of b
let b = A - a;
let res = [ 0, 0 ];
let res1 = [ a, b ];
// Edge Cases
if (a == 0 || b == 0)
return res;
else if ((a + b) > Math.pow(10, 3)
|| (a - b) < Math.pow(-10, 3))
return res;
// 1st Condition, C = a*b
else if ((a * b == C) && (Math.floor(a / b) == D)
&& (a % b == E)
|| (a * b == C) && (Math.floor(a / b) == E)
&& (a % b == D))
return res1;
// 2nd Condition, D = a*b
else if ((a * b == D) && (Math.floor(a / b) == C)
&& (a % b == E)
|| (a * b == D) && (Math.floor(a / b) == E)
&& (a % b == C))
return res1;
// 3rd Condition, E = a*b
else if ((a * b == E) && (Math.floor(a / b) == C)
&& (a % b == D)
|| (a * b == E) && (Math.floor(a / b) == D)
&& (a % b == C))
return res1;
// Pairs are not valid then return 0
else
return res;
}
}
// Function to find two integers X and Y
function findNum(arr)
{
let p = new Array(2);
let flag = 0;
for (let i = 0; i <= 4; i++) {
// Swapping for every
// X + Y combination
let tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
for (let j = 1; j <= 4; j++) {
// Swapping for every
// X - Y combination
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// Checking for valid X and Y
p = isValid(arr[0], arr[1], arr[2], arr[3],
arr[4]);
// If both are not -1 then
// we found X and Y
if ((p[0] != 0) && (p[1] != 0)) {
// Set Flag = true
flag = 1;
// Print the values in order
// i.e., X and Y
document.write(p[0] + " " + p[1]);
}
// Backtracking
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// Backtracking
tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
// X and Y are found
if (flag != 0)
break;
}
// If flag is 0 then X and Y
// can't be possible
if (flag == 0)
document.write("0 0");
}
// Driver code
let N = 5;
let arr = [ -1, 0, 4, 9, 20 ];
// Function call
findNum(arr);
// This code is contributed by sanjoy_62.
</script>
Producción
4 5
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA