Dada una array de enteros positivos. Necesitamos hacer que la array dada sea un ‘Palíndrome’. La única operación permitida es la “fusión” (de dos elementos adyacentes). Fusionar dos elementos adyacentes significa reemplazarlos con su suma. La tarea es encontrar el número mínimo de operaciones de combinación requeridas para hacer que la array dada sea un ‘Palíndrome’.
Para convertir cualquier array en un palíndromo, simplemente podemos aplicar la operación de combinación n-1 veces, donde n es el tamaño de la array (porque una array de un solo elemento siempre es palindrómica, similar a una string de un solo carácter). En ese caso, el tamaño de la array se reducirá a 1. Pero en este problema, se nos pide que lo hagamos en el mínimo número de operaciones.
C++
// C++ program to find number of operations
// to make an array palindrome
#include <bits/stdc++.h>
using namespace std;
// Returns minimum number of count operations
// required to make arr[] palindrome
int findMinOps(int arr[], int n)
{
int ans = 0; // Initialize result
// Start from two corners
for (int i=0,j=n-1; i<=j;)
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if (arr[i] == arr[j])
{
i++;
j--;
}
// If left element is greater, then
// we merge right two elements
else if (arr[i] > arr[j])
{
// need to merge from tail.
j--;
arr[j] += arr[j+1] ;
ans++;
}
// Else we merge left two elements
else
{
i++;
arr[i] += arr[i-1];
ans++;
}
}
return ans;
}
// Driver program to test above
int main()
{
int arr[] = {1, 4, 5, 9, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of minimum operations is "
<< findMinOps(arr, n) << endl;
return 0;
}
Java
// Java program to find number of operations
// to make an array palindrome
class GFG
{
// Returns minimum number of count operations
// required to make arr[] palindrome
static int findMinOps(int[] arr, int n)
{
int ans = 0; // Initialize result
// Start from two corners
for (int i=0,j=n-1; i<=j;)
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if (arr[i] == arr[j])
{
i++;
j--;
}
// If left element is greater, then
// we merge right two elements
else if (arr[i] > arr[j])
{
// need to merge from tail.
j--;
arr[j] += arr[j+1] ;
ans++;
}
// Else we merge left two elements
else
{
i++;
arr[i] += arr[i-1];
ans++;
}
}
return ans;
}
// Driver method to test the above function
public static void main(String[] args)
{
int arr[] = new int[]{1, 4, 5, 9, 1} ;
System.out.println("Count of minimum operations is "+
findMinOps(arr, arr.length));
}
}
Python3
# Python program to find number of operations
# to make an array palindrome
# Returns minimum number of count operations
# required to make arr[] palindrome
def findMinOps(arr, n):
ans = 0 # Initialize result
# Start from two corners
i,j = 0,n-1
while i<=j:
# If corner elements are same,
# problem reduces arr[i+1..j-1]
if arr[i] == arr[j]:
i += 1
j -= 1
# If left element is greater, then
# we merge right two elements
elif arr[i] > arr[j]:
# need to merge from tail.
j -= 1
arr[j] += arr[j+1]
ans += 1
# Else we merge left two elements
else:
i += 1
arr[i] += arr[i-1]
ans += 1
return ans
# Driver program to test above
arr = [1, 4, 5, 9, 1]
n = len(arr)
print("Count of minimum operations is " + str(findMinOps(arr, n)))
# This code is contributed by Pratik Chhajer
C#
// C# program to find number of operations
// to make an array palindrome
using System;
class GFG
{
// Returns minimum number of count operations
// required to make arr[] palindrome
static int findMinOps(int []arr, int n)
{
int ans = 0; // Initialize result
// Start from two corners
for (int i = 0, j = n - 1; i <= j;)
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if (arr[i] == arr[j])
{
i++;
j--;
}
// If left element is greater, then
// we merge right two elements
else if (arr[i] > arr[j])
{
// need to merge from tail.
j--;
arr[j] += arr[j + 1] ;
ans++;
}
// Else we merge left two elements
else
{
i++;
arr[i] += arr[i-1];
ans++;
}
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = new int[]{1, 4, 5, 9, 1} ;
Console.Write("Count of minimum operations is " +
findMinOps(arr, arr.Length));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find number
// of operations to make an
// array palindrome
// Returns minimum number of
// count operations required
// to make arr[] palindrome
function findMinOps($arr, $n)
{
// Initialize result
$ans = 1;
// Start from two corners
for ($i = 0, $j = $n - 1; $i <= $j😉
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if ($arr[$i] == $arr[$j])
{
$i++;
$j--;
}
// If left element is greater, then
// we merge right two elements
else if ($arr[$i] > $arr[$j])
{
// need to merge from tail.
$j--;
$arr[$j] += $arr[$j + 1] ;
$ans++;
}
// Else we merge
// left two elements
else
{
$i++;
$arr[$i] += $arr[$i - 1];
$ans++;
}
}
return $ans;
}
// Driver Code
$arr[] = array(1, 4, 5, 9, 1);
$n = sizeof($arr);
echo "Count of minimum operations is ",
findMinOps($arr, $n) ;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find number of operations
// to make an array palindrome
// Returns minimum number of count operations
// required to make arr[] palindrome
function findMinOps(arr, n)
{
let ans = 0; // Initialize result
// Start from two corners
for (let i=0,j=n-1; i<=j;)
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if (arr[i] == arr[j])
{
i++;
j--;
}
// If left element is greater, then
// we merge right two elements
else if (arr[i] > arr[j])
{
// need to merge from tail.
j--;
arr[j] += arr[j+1] ;
ans++;
}
// Else we merge left two elements
else
{
i++;
arr[i] += arr[i-1];
ans++;
}
}
return ans;
}
// Driver Code
let arr = [1, 4, 5, 9, 1];
document.write("Count of minimum operations is "+
findMinOps(arr, arr.length));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA