Dada una array arr que contiene N elementos enteros, la tarea es contar el número mínimo de elementos que deben cambiarse de modo que todos los elementos (después de la reorganización adecuada) formen los primeros N términos de la serie de Fibonacci.
Ejemplos:
Entrada: arr[] = {4, 1, 2, 1, 3, 7}
Salida: 2
4 y 7 deben cambiarse a 5 y 8 para formar los primeros N(6) términos de la serie de Fibonacci.
Entrada: arr[] = {5, 3, 1, 1, 2, 8, 11}
Salida: 1
11 debe cambiarse a 13.
Acercarse:
- Inserte los primeros N elementos de la serie de Fibonacci en un conjunto múltiple.
- Luego, recorra la array de izquierda a derecha y verifique si el elemento actual está presente en el conjunto múltiple.
- Si el elemento está presente en el conjunto múltiple, elimínelo.
- La respuesta final será el tamaño del multiconjunto final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum number
// of elements the need to be changed
// to get first N numbers of Fibonacci series
#include <bits/stdc++.h>
using namespace std;
// Function that finds minimum changes required
int fibonacciArray(int arr[], int n)
{
multiset<int> s;
// a and b are first two
// fibonacci numbers
int a = 1, b = 1;
int c;
// insert first n fibonacci elements to set
s.insert(a);
if (n >= 2)
s.insert(b);
for (int i = 0; i < n - 2; i++) {
c = a + b;
s.insert(c);
a = b;
b = c;
}
multiset<int>::iterator it;
for (int i = 0; i < n; i++) {
// if fibonacci element is present
// in the array then remove it from set
it = s.find(arr[i]);
if (it != s.end())
s.erase(it);
}
// return the remaining number of
// elements in the set
return s.size();
}
// Driver code
int main()
{
int arr[] = { 3, 1, 21, 4, 2, 1, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << fibonacciArray(arr, n);
return 0;
}
Java
// Java program to find the minimum number
// of elements the need to be changed
// to get first N numbers of Fibonacci series
import java.util.*;
class geeks
{
// Function that finds minimum changes required
public static int fibonacciArray(int[] arr, int n)
{
Set<Integer> s = new HashSet<Integer>();
// a and b are first two
// fibonacci numbers
int a = 1, b = 1;
int c;
// insert first n fibonacci elements to set
s.add(a);
if (n > 2)
s.add(b);
for (int i = 0; i < n - 2; i++)
{
c = a + b;
s.add(c);
a = b;
b = c;
}
for (int i = 0; i < n; i++)
{
// if fibonacci element is present
// in the array then remove it from set
if (s.contains(arr[i]))
s.remove(arr[i]);
}
// return the remaining number of
// elements in the set
return s.size();
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 3, 1, 21, 4, 2, 1, 8, 9 };
int n = arr.length;
System.out.print(fibonacciArray(arr, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find the minimum number # of elements the need to be changed # to get first N numbers of Fibonacci series # Function that finds minimum changes required def fibonacciArray(arr, n): s = set() # a and b are first two # fibonacci numbers a, b = 1, 1 # insert first n fibonacci elements to set s.add(a) if n >= 2: s.add(b) for i in range(0, n - 2): c = a + b s.add(c) a, b = b, c for i in range(0, n): # if fibonacci element is present in # the array then remove it from set if arr[i] in s: s.remove(arr[i]) # return the remaining number # of elements in the set return len(s) # Driver code if __name__ == "__main__": arr = [3, 1, 21, 4, 2, 1, 8, 9] n = len(arr) print(fibonacciArray(arr, n)) # This code is contributed by Rituraj Jain
C#
// C# program to find the minimum number
// of elements the need to be changed
// to get first N numbers of Fibonacci series
using System;
using System.Collections.Generic;
public class geeks
{
// Function that finds minimum changes required
public static int fibonacciArray(int[] arr, int n)
{
HashSet<int> s = new HashSet<int>();
// a and b are first two
// fibonacci numbers
int a = 1, b = 1;
int c;
// insert first n fibonacci elements to set
s.Add(a);
if (n > 2)
s.Add(b);
for (int i = 0; i < n - 2; i++)
{
c = a + b;
s.Add(c);
a = b;
b = c;
}
for (int i = 0; i < n; i++)
{
// if fibonacci element is present
// in the array then remove it from set
if (s.Contains(arr[i]))
s.Remove(arr[i]);
}
// return the remaining number of
// elements in the set
return s.Count;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 1, 21, 4, 2, 1, 8, 9 };
int n = arr.Length;
Console.WriteLine(fibonacciArray(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the minimum number
// of elements the need to be changed
// to get first N numbers of Fibonacci series
// Function that finds minimum changes required
function fibonacciArray(arr, n) {
let s = new Set();
// a and b are first two
// fibonacci numbers
let a = 1, b = 1;
let c;
// insert first n fibonacci elements to set
s.add(a);
if (n > 2)
s.add(b);
for (let i = 0; i < n - 2; i++) {
c = a + b;
s.add(c);
a = b;
b = c;
}
for (let i = 0; i < n; i++) {
// if fibonacci element is present
// in the array then remove it from set
if (s.has(arr[i]))
s.delete(arr[i]);
}
// return the remaining number of
// elements in the set
return s.size;
}
// Driver Code
let arr = [3, 1, 21, 4, 2, 1, 8, 9];
let n = arr.length;
document.write(fibonacciArray(arr, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
2
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