Pares distintos de arrays dadas (a[i], b[j]) tales que (a[i] + b[j]) es un número de Fibonacci

Dadas dos arrays a[] y b[] , la tarea es contar los pares (a[i], b[j]) de modo que (a[i] + b[j]) sea un número de Fibonacci. Tenga en cuenta que (a, b) es igual a (b, a) y se contará una vez. 
Los primeros números de Fibonacci son: 
 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, …..

Ejemplos: 
 

Entrada: a[] = {99, 1, 33, 2}, b[] = {1, 11, 2} 
Salida:
pares distintos totales son (1, 1), (1, 2), (33, 1 ) y (2, 11)
Entrada: a[] = {5, 0, 8}, b[] = {0, 9} 
Salida:
 

Acercarse: 
 

  • Tome un juego vacío .
  • Ejecute dos bucles anidados para generar todos los pares posibles de las dos arrays tomando un elemento de la primera array (llámelo a) y uno de la segunda array (llámelo b).
  • Aplique la prueba de Fibonacci en (a + b) , es decir, para que un número x sea un número de Fibonacci, cualquiera de 5 * x 2 + 4 o 5 * x 2 – 4 debe ser un cuadrado perfecto.
  • Si es el número de Fibonacci, presione (a, b) en el conjunto, si a < b o (b, a) si b < a . Esto se hace para evitar la duplicación.
  • El tamaño del conjunto al final es el recuento total de pares válidos.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if
// x is a perfect square
bool isPerfectSquare(long double x)
{
    // Find floating point value of
    // square root of x
    long double sr = sqrt(x);
 
    // If square root is an integer
    return ((sr - floor(sr)) == 0);
}
 
// Function that returns true if
// n is a Fibonacci Number
bool isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4)
           || isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of distinct pairs
// from the given array such that the sum of the
// pair elements is a Fibonacci number
int totalPairs(int a[], int b[], int n, int m)
{
    // Set is used to avoid duplicate pairs
    set<pair<int, int> > s;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            // If sum is a Fibonacci number
            if (isFibonacci(a[i] + b[j]) == true) {
                if (a[i] < b[j])
                    s.insert(make_pair(a[i], b[j]));
                else
                    s.insert(make_pair(b[j], a[i]));
            }
        }
    }
 
    // Return the size of the set
    return s.size();
}
 
// Driver code
int main()
{
    int a[] = { 99, 1, 33, 2 };
    int b[] = { 1, 11, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    int m = sizeof(b) / sizeof(b[0]);
 
    cout << totalPairs(a, b, n, m);
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function that returns true if
// x is a perfect square
static boolean isPerfectSquare(double x)
{
    // Find floating point value of
    // square root of x
    double sr = Math.sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function that returns true if
// n is a Fibonacci Number
static boolean isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4) ||
           isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of distinct pairs
// from the given array such that the sum of the
// pair elements is a Fibonacci number
static int totalPairs(int a[], int b[],
                      int n, int m)
{
    // Set is used to avoid duplicate pairs
    List<pair> s = new LinkedList<>();
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
 
            // If sum is a Fibonacci number
            if (isFibonacci(a[i] + b[j]) == true)
            {
                 
                if (a[i] < b[j])
                {
                    if(checkDuplicate(s, new pair(a[i], b[j])))
                        s.add(new pair(a[i], b[j]));
                }
                else
                {
                    if(checkDuplicate(s, new pair(b[j], a[i])))
                        s.add(new pair(b[j], a[i]));
                }
            }
        }
    }
 
    // Return the size of the set
    return s.size();
}
 
static boolean checkDuplicate(List<pair> pairList,
                                    pair newPair)
{
    for(pair p: pairList)
    {
        if(p.first == newPair.first &&
           p.second == newPair.second)
            return false;
    }
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 99, 1, 33, 2 };
    int b[] = { 1, 11, 2 };
    int n = a.length;
    int m = b.length;
 
    System.out.println(totalPairs(a, b, n, m));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach
from math import sqrt,floor
 
# Function that returns true if
# x is a perfect square
def isPerfectSquare(x) :
 
    # Find floating point value of
    # square root of x
    sr = sqrt(x)
 
    # If square root is an integer
    return ((sr - floor(sr)) == 0)
 
# Function that returns true if
# n is a Fibonacci Number
def isFibonacci(n ) :
 
    return (isPerfectSquare(5 * n * n + 4) or
            isPerfectSquare(5 * n * n - 4))
 
# Function to return the count of distinct pairs
# from the given array such that the sum of the
# pair elements is a Fibonacci number
def totalPairs(a, b, n, m) :
 
    # Set is used to avoid duplicate pairs
    s = set();
 
    for i in range(n) :
        for j in range(m) :
 
            # If sum is a Fibonacci number
            if (isFibonacci(a[i] + b[j]) == True) :
                if (a[i] < b[j]) :
                    s.add((a[i], b[j]));
                else :
                    s.add((b[j], a[i]));
 
    # Return the size of the set
    return len(s);
 
# Driver code
if __name__ == "__main__" :
     
    a = [ 99, 1, 33, 2 ];
    b = [ 1, 11, 2 ];
    n = len(a);
    m = len(b);
 
    print(totalPairs(a, b, n, m));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;            
 
class GFG
{
public class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function that returns true if
// x is a perfect square
static bool isPerfectSquare(double x)
{
    // Find floating point value of
    // square root of x
    double sr = Math.Sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.Floor(sr)) == 0);
}
 
// Function that returns true if
// n is a Fibonacci Number
static bool isFibonacci(int n)
{
    return isPerfectSquare(5 * n * n + 4) ||
           isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of distinct pairs
// from the given array such that the sum of the
// pair elements is a Fibonacci number
static int totalPairs(int []a, int []b,
                      int n, int m)
{
    // Set is used to avoid duplicate pairs
    List<pair> s = new List<pair>();
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
 
            // If sum is a Fibonacci number
            if (isFibonacci(a[i] + b[j]) == true)
            {
                 
                if (a[i] < b[j])
                {
                    if(checkDuplicate(s, new pair(a[i], b[j])))
                                   s.Add(new pair(a[i], b[j]));
                }
                else
                {
                    if(checkDuplicate(s, new pair(b[j], a[i])))
                                   s.Add(new pair(b[j], a[i]));
                }
            }
        }
    }
 
    // Return the size of the set
    return s.Count;
}
 
static bool checkDuplicate(List<pair> pairList,
                                      pair newPair)
{
    foreach(pair p in pairList)
    {
        if(p.first == newPair.first &&
           p.second == newPair.second)
            return false;
    }
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 99, 1, 33, 2 };
    int []b = { 1, 11, 2 };
    int n = a.Length;
    int m = b.Length;
 
    Console.WriteLine(totalPairs(a, b, n, m));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if
// x is a perfect square
function isPerfectSquare(x)
{
    // Find floating point value of
    // square root of x
    var sr = Math.sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function that returns true if
// n is a Fibonacci Number
function isFibonacci(n)
{
    return isPerfectSquare(5 * n * n + 4)
           || isPerfectSquare(5 * n * n - 4);
}
 
// Function to return the count of distinct pairs
// from the given array such that the sum of the
// pair elements is a Fibonacci number
function totalPairs(a, b, n, m)
{
    // Set is used to avoid duplicate pairs
    var s = new Set();
 
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < m; j++) {
 
            // If sum is a Fibonacci number
            if (isFibonacci(a[i] + b[j])) {
                if (a[i] < b[j])
                {
                    var tmp = a[i]+" "+b[j];
                    s.add(tmp);
                }
                else
                {
                    var tmp = b[j]+" "+a[i];
                    s.add(tmp);
                }
            }
        }
    }
 
    // Return the size of the set
    return s.size;
}
 
// Driver code
var a = [99, 1, 33, 2 ];
var b = [1, 11, 2 ];
var n = a.length;
var m = b.length;
document.write( totalPairs(a, b, n, m));
 
</script>
Producción: 

4

 

Publicación traducida automáticamente

Artículo escrito por Shashank_Sharma 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 *