Encuentra X e Y a partir de su suma, diferencia, producto, división y resto

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *