Dada una array arr[] , la tarea es encontrar el número mínimo de incrementos o decrementos de 1 necesarios para convertir la array en una Serie de Fibonacci . Si no es posible, imprima -1 .
Nota: Cada elemento de la array se puede incrementar o disminuir solo una vez.
Ejemplos:
Entrada: arr[] = {4, 8, 9, 17, 21}
Salida: 3
Explicación:
La array se puede convertir en una serie de Fibonacci en tres movimientos:
Convertir 4 en 3, arr[] = {3, 8, 9 , 17, 21}
Convierte 8 en 7, arr[] = {3, 7, 9, 17, 21}
Convierte 9 en 10, arr[] = {3, 7, 10, 17, 21}Entrada: arr[] = {3, 8, 7, 2}
Salida: -1
Explicación:
la array dada no se puede convertir en una serie de Fibonacci.
Enfoque: La idea para resolver el problema es utilizar el hecho de que los dos primeros elementos de una Serie de Fibonacci son suficientes para calcular la diferencia común de la Serie de Fibonacci y, por lo tanto, los elementos posteriores. Así que verifica todas las permutaciones de operaciones en los dos primeros números y calcula los movimientos mínimos para convertir el resto de los elementos en la serie de Fibonacci.
Siga los pasos a continuación para implementar el enfoque anterior:
- Si el número de elementos en la array es menor a 3, entonces ya es una serie de Fibonacci .
- De lo contrario, pruebe todas las permutaciones de los dos primeros elementos:
- Para cada permutación, calcule el número de operaciones para el resto de los elementos de la array:
- Si no es posible cambiar el elemento en una operación como máximo, entonces la array no se puede convertir en una serie de Fibonacci.
- De lo contrario, actualice el número requerido de operaciones.
- Actualice la respuesta con el número de operaciones.
- Para cada permutación, calcule el número de operaciones para el resto de los elementos de la array:
- Devuelve la respuesta.
A continuación se muestra la implementación de nuestro enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate minimum
// number of moves to make the
// sequence a Fibonacci series
int minMoves(vector<int> arr)
{
int N = arr.size();
// If number of elements
// is less than 3
if (N <= 2)
return 0;
// Initialize the value
// of the result
int ans = INT_MAX;
// Try all permutations of
// the first two elements
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
// Value of first element
// after operation
int num1 = arr[0] + i;
// Value of second element
// after operation
int num2 = arr[1] + j;
int flag = 1;
int moves = abs(i) + abs(j);
// Calculate number of moves
// for rest of the elements
// of the array
for (int idx = 2; idx < N; idx++) {
// Element at idx index
int num = num1 + num2;
// If it is not possible
// to change the element
// in atmost one move
if (abs(arr[idx] - num) > 1)
flag = 0;
// Otherwise
else
moves += abs(arr[idx] - num);
num1 = num2;
num2 = num;
}
// Update the answer
if (flag)
ans = min(ans, moves);
}
}
// Return the answer
if (ans == INT_MAX)
return -1;
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 4, 8, 9, 17, 27 };
cout << minMoves(arr) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate minimum
// number of moves to make the
// sequence a Fibonacci series
static int minMoves(int []arr)
{
int N = arr.length;
// If number of elements
// is less than 3
if (N <= 2)
return 0;
// Initialize the value
// of the result
int ans = Integer.MAX_VALUE;
// Try all permutations of
// the first two elements
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
// Value of first element
// after operation
int num1 = arr[0] + i;
// Value of second element
// after operation
int num2 = arr[1] + j;
int flag = 1;
int moves = Math.abs(i) + Math.abs(j);
// Calculate number of moves
// for rest of the elements
// of the array
for (int idx = 2; idx < N; idx++)
{
// Element at idx index
int num = num1 + num2;
// If it is not possible
// to change the element
// in atmost one move
if (Math.abs(arr[idx] - num) > 1)
flag = 0;
// Otherwise
else
moves += Math.abs(arr[idx] - num);
num1 = num2;
num2 = num;
}
// Update the answer
if (flag > 0)
ans = Math.min(ans, moves);
}
}
// Return the answer
if (ans == Integer.MAX_VALUE)
return -1;
return ans;
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 4, 8, 9, 17, 27 };
System.out.print(minMoves(arr));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach import sys # Function to calculate minimum # number of moves to make the # sequence a Fibonacci series def minMoves(arr): N = len(arr) # If number of elements # is less than 3 if (N <= 2): return 0 # Initialize the value # of the result ans = sys.maxsize # Try all permutations of # the first two elements for i in range(-1, 2): for j in range(-1, 2): # Value of first element # after operation num1 = arr[0] + i # Value of second element # after operation num2 = arr[1] + j flag = 1 moves = abs(i) + abs(j) # Calculate number of moves # for rest of the elements # of the array for idx in range(2, N): # Element at idx index num = num1 + num2 # If it is not possible # to change the element # in atmost one move if (abs(arr[idx] - num) > 1): flag = 0 # Otherwise else: moves += abs(arr[idx] - num) num1 = num2 num2 = num # Update the answer if (flag): ans = min(ans, moves) # Return the answer if (ans == sys.maxsize): return -1 return ans # Driver Code if __name__ == "__main__": arr = [4, 8, 9, 17, 27] print(minMoves(arr)) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
// Function to calculate minimum
// number of moves to make the
// sequence a Fibonacci series
class GFG{
static int minMoves(List<int> arr)
{
int N = arr.Count;
// If number of elements
// is less than 3
if (N <= 2)
return 0;
// Initialize the value
// of the result
int ans = Int32.MaxValue;
// Try all permutations of
// the first two elements
for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)
{
// Value of first element
// after operation
int num1 = arr[0] + i;
// Value of second element
// after operation
int num2 = arr[1] + j;
int flag = 1;
int moves = Math.Abs(i) + Math.Abs(j);
// Calculate number of moves
// for rest of the elements
// of the array
for(int idx = 2; idx < N; idx++)
{
// Element at idx index
int num = num1 + num2;
// If it is not possible
// to change the element
// in atmost one move
if (Math.Abs(arr[idx] - num) > 1)
flag = 0;
// Otherwise
else
moves += Math.Abs(arr[idx] - num);
num1 = num2;
num2 = num;
}
// Update the answer
if (flag != 0)
ans = Math.Min(ans, moves);
}
}
// Return the answer
if (ans == Int32.MaxValue)
return -1;
return ans;
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){ 4, 8, 9, 17, 27 };
Console.WriteLine(minMoves(arr));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// javascript program of the above approach
// Function to calculate minimum
// number of moves to make the
// sequence a Fibonacci series
function minMoves(arr)
{
let N = arr.length;
// If number of elements
// is less than 3
if (N <= 2)
return 0;
// Initialize the value
// of the result
let ans = Number.MAX_VALUE;
// Try all permutations of
// the first two elements
for (let i = -1; i <= 1; i++)
{
for (let j = -1; j <= 1; j++)
{
// Value of first element
// after operation
let num1 = arr[0] + i;
// Value of second element
// after operation
let num2 = arr[1] + j;
let flag = 1;
let moves = Math.abs(i) + Math.abs(j);
// Calculate number of moves
// for rest of the elements
// of the array
for (let idx = 2; idx < N; idx++)
{
// Element at idx index
let num = num1 + num2;
// If it is not possible
// to change the element
// in atmost one move
if (Math.abs(arr[idx] - num) > 1)
flag = 0;
// Otherwise
else
moves += Math.abs(arr[idx] - num);
num1 = num2;
num2 = num;
}
// Update the answer
if (flag > 0)
ans = Math.min(ans, moves);
}
}
// Return the answer
if (ans == Number.MAX_VALUE)
return -1;
return ans;
}
// Driver Code
let arr = [ 4, 8, 9, 17, 27 ];
document.write(minMoves(arr));
// This code is contributed by chinmoy1997pal.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA