Posted on by Kalkicode
Code Array

Find minimum number of merge operations to make an array palindrome

Here given code implementation process.

/*
C program for
Find minimum number of merge operations to make an array palindrome
*/
#include <stdio.h>
// Display array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d",arr[i]);
}
}

void minMergePalindrome(int arr[], int n)
{
if(n<=0)
{
return;
}

// Auxiliary variables
int operation = 0;

int start = 0;

int last = n-1;

int temp[n];

// Copy array element
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}

while(start < last)
{

if(temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start ++;
last --;
}
else if(temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last-1] = temp[last-1] + temp[last];

// Reduce last boundary position
last --;

// increase operation
operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start+1] = temp[start+1] + temp[start];

// Increase start boundary position
start ++;
// Increase operation
operation++;
}
}

printf("\n Array  : ");

printArray(arr, n);

printf("\n Result : %d",operation);
}
int main(int argc, char const *argv[])
{
int arr1[]= { 2, 1, 4, 3 , 5,  2, 1, 2};
int arr2[]= {4, 3, 2, 3, 4, 7};
int arr3[]= {1, 2, 1};
int arr4[]= {1, 4, 1 , 5, 1};
int arr5[]= {1, 2, 3, 1};
// Test A
int n = sizeof(arr1)/sizeof(arr1[0]);
/*

[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -

2, 1 [4 + 3] ,  7,   1, 2
➁

2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation

*/
minMergePalindrome(arr1,n);

// Test B
n = sizeof(arr2)/sizeof(arr2[0]);
/*

[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation

7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
minMergePalindrome(arr2,n);

// Test C
n = sizeof(arr3)/sizeof(arr3[0]);
/*

[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
minMergePalindrome(arr3,n);

// Test D
n = sizeof(arr4)/sizeof(arr4[0]);
/*

[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
minMergePalindrome(arr4,n);

// Test E
n = sizeof(arr5)/sizeof(arr5[0]);
/*

[1 , [2 + 3], 1]
➀

Result = 1
*/
minMergePalindrome(arr5,n);
return 0;
}

Output

Array  :  2 1 4 3 5 2 1 2
Result : 2
Array  :  4 3 2 3 4 7
Result : 3
Array  :  1 2 1
Result : 0
Array  :  1 4 1 5 1
Result : 1
Array  :  1 2 3 1
Result : 1
// Java program for
// Find minimum number of merge operations to make an array palindrome
public class PalindromeOperation
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public void minMergePalindrome(int[] arr, int n)
{
if (n <= 0)
{
return;
}
// Auxiliary variables
int operation = 0;
int start = 0;
int last = n - 1;
int[] temp = new int[n];
// Copy array element
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start++;
last--;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last--;
// increase operation
operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start++;
// Increase operation
operation++;
}
}
System.out.print("\n Array : ");
printArray(arr, n);
System.out.print("\n Result : " + operation);
}
public static void main(String[] args)
{
int[] arr1 = {
2 , 1 , 4 , 3 , 5 , 2 , 1 , 2
};
int[] arr2 = {
4 , 3 , 2 , 3 , 4 , 7
};
int[] arr3 = {
1 , 2 , 1
};
int[] arr4 = {
1 , 4 , 1 , 5 , 1
};
int[] arr5 = {
1 , 2 , 3 , 1
};
// Test A
int n = arr1.length;
/*

[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -

2, 1 [4 + 3] ,  7,   1, 2
➁

2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation

*/
// Test B
n = arr2.length;
/*

[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation

7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.length;
/*

[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.length;
/*

[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.length;
/*

[1 , [2 + 3], 1]
➀

Result = 1
*/
}
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
#include <iostream>

using namespace std;
// C++ program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
{
public:
// Display array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
void minMergePalindrome(int arr[], int n)
{
if (n <= 0)
{
return;
}
// Auxiliary variables
int operation = 0;
int start = 0;
int last = n - 1;
int temp[n];
// Copy array element
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start++;
last--;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last--;
// increase operation
operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start++;
// Increase operation
operation++;
}
}
cout << "\n Array : ";
this->printArray(arr, n);
cout << "\n Result : " << operation;
}
};
int main()
{
int arr1[] = {
2 , 1 , 4 , 3 , 5 , 2 , 1 , 2
};
int arr2[] = {
4 , 3 , 2 , 3 , 4 , 7
};
int arr3[] = {
1 , 2 , 1
};
int arr4[] = {
1 , 4 , 1 , 5 , 1
};
int arr5[] = {
1 , 2 , 3 , 1
};
// Test A
int n = sizeof(arr1) / sizeof(arr1[0]);
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = sizeof(arr3) / sizeof(arr3[0]);
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = sizeof(arr4) / sizeof(arr4[0]);
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = sizeof(arr5) / sizeof(arr5[0]);
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
return 0;
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
// Include namespace system
using System;
// Csharp program for
// Find minimum number of merge operations to make an array palindrome
public class PalindromeOperation
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public void minMergePalindrome(int[] arr, int n)
{
if (n <= 0)
{
return;
}
// Auxiliary variables
int operation = 0;
int start = 0;
int last = n - 1;
int[] temp = new int[n];
// Copy array element
for (int i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start++;
last--;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last--;
// increase operation
operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start++;
// Increase operation
operation++;
}
}
Console.Write("\n Array : ");
this.printArray(arr, n);
Console.Write("\n Result : " + operation);
}
public static void Main(String[] args)
{
int[] arr1 = {
2 , 1 , 4 , 3 , 5 , 2 , 1 , 2
};
int[] arr2 = {
4 , 3 , 2 , 3 , 4 , 7
};
int[] arr3 = {
1 , 2 , 1
};
int[] arr4 = {
1 , 4 , 1 , 5 , 1
};
int[] arr5 = {
1 , 2 , 3 , 1
};
// Test A
int n = arr1.Length;
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = arr2.Length;
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.Length;
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.Length;
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.Length;
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
package main
import "fmt"
// Go program for
// Find minimum number of merge operations to make an array palindrome

// Display array elements
func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
func minMergePalindrome(arr[] int, n int) {
if n <= 0 {
return
}
// Auxiliary variables
var operation int = 0
var start int = 0
var last int = n - 1
var temp = make([] int, n)
// Copy array element
for i := 0 ; i < n ; i++ {
temp[i] = arr[i]
}
for (start < last) {
if temp[start] == temp[last] {
// When boundary element is similar
// Change boundary position
start++
last--
} else if temp[start] > temp[last] {
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last]
// Reduce last boundary position
last--
// increase operation
operation++
} else {
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start]
// Increase start boundary position
start++
// Increase operation
operation++
}
}
fmt.Print("\n Array : ")
printArray(arr, n)
fmt.Print("\n Result : ", operation)
}
func main() {

var arr1 = [] int { 2, 1, 4, 3 , 5,  2, 1, 2}
var arr2 = [] int { 4, 3, 2, 3, 4, 7 }
var arr3 = [] int { 1, 2, 1 }
var arr4 = [] int { 1, 4, 1 , 5, 1 }
var arr5 = [] int { 1, 2, 3, 1 }
// Test A
var n int = len(arr1)
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
minMergePalindrome(arr1, n)
// Test B
n = len(arr2)
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
minMergePalindrome(arr2, n)
// Test C
n = len(arr3)
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
minMergePalindrome(arr3, n)
// Test D
n = len(arr4)
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
minMergePalindrome(arr4, n)
// Test E
n = len(arr5)
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
minMergePalindrome(arr5, n)
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
<?php
// Php program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
{
// Display array elements
public	function printArray(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
}
public	function minMergePalindrome(\$arr, \$n)
{
if (\$n <= 0)
{
return;
}
// Auxiliary variables
\$operation = 0;
\$start = 0;
\$last = \$n - 1;
\$temp = array_fill(0, \$n, 0);
// Copy array element
for (\$i = 0; \$i < \$n; ++\$i)
{
\$temp[\$i] = \$arr[\$i];
}
while (\$start < \$last)
{
if (\$temp[\$start] == \$temp[\$last])
{
// When boundary element is similar
// Change boundary position
\$start++;
\$last--;
}
else if (\$temp[\$start] > \$temp[\$last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
\$temp[\$last - 1] = \$temp[\$last - 1] + \$temp[\$last];
// Reduce last boundary position
\$last--;
// increase operation
\$operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
\$temp[\$start + 1] = \$temp[\$start + 1] + \$temp[\$start];
// Increase start boundary position
\$start++;
// Increase operation
\$operation++;
}
}
echo("\n Array : ");
\$this->printArray(\$arr, \$n);
echo("\n Result : ".\$operation);
}
}

function main()
{
\$arr1 = array(2, 1, 4, 3, 5, 2, 1, 2);
\$arr2 = array(4, 3, 2, 3, 4, 7);
\$arr3 = array(1, 2, 1);
\$arr4 = array(1, 4, 1, 5, 1);
\$arr5 = array(1, 2, 3, 1);
// Test A
\$n = count(\$arr1);
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
\$n = count(\$arr2);
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
\$n = count(\$arr3);
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
\$n = count(\$arr4);
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
\$n = count(\$arr5);
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}
main();

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
// Node JS program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
{
// Display array elements
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
minMergePalindrome(arr, n)
{
if (n <= 0)
{
return;
}
// Auxiliary variables
var operation = 0;
var start = 0;
var last = n - 1;
var temp = Array(n).fill(0);
// Copy array element
for (var i = 0; i < n; ++i)
{
temp[i] = arr[i];
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start++;
last--;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last--;
// increase operation
operation++;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start++;
// Increase operation
operation++;
}
}
process.stdout.write("\n Array : ");
this.printArray(arr, n);
process.stdout.write("\n Result : " + operation);
}
}

function main()
{
var arr1 = [2, 1, 4, 3, 5, 2, 1, 2];
var arr2 = [4, 3, 2, 3, 4, 7];
var arr3 = [1, 2, 1];
var arr4 = [1, 4, 1, 5, 1];
var arr5 = [1, 2, 3, 1];
// Test A
var n = arr1.length;
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = arr2.length;
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.length;
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.length;
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.length;
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}
main();

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
#  Python 3 program for
#  Find minimum number of merge operations to make an array palindrome
class PalindromeOperation :
#  Display list elements
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

def minMergePalindrome(self, arr, n) :
if (n <= 0) :
return

#  Auxiliary variables
operation = 0
start = 0
last = n - 1
temp = [0] * (n)
i = 0
#  Copy list element
while (i < n) :
temp[i] = arr[i]
i += 1

while (start < last) :
if (temp[start] == temp[last]) :
#  When boundary element is similar
#  Change boundary position
start += 1
last -= 1
elif (temp[start] > temp[last]) :
#  When left side boundary element is
#  greater than right side boundary element.
#  Change last boundary -1 element
#  by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last]
#  Reduce last boundary position
last -= 1
#  increase operation
operation += 1
else :
#  Change left side next element is
#  Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start]
#  Increase start boundary position
start += 1
#  Increase operation
operation += 1

print("\n Array : ", end = "")
self.printArray(arr, n)
print("\n Result : ", operation, end = "")

def main() :
arr1 = [2, 1, 4, 3, 5, 2, 1, 2]
arr2 = [4, 3, 2, 3, 4, 7]
arr3 = [1, 2, 1]
arr4 = [1, 4, 1, 5, 1]
arr5 = [1, 2, 3, 1]
#  Test A
n = len(arr1)
#    [2, 1 , 4 , 3 , 5 , 2, 1, 2]
#     -  -                  -  -
#    [Note boundary element 2, 1 is palindrome]
#    2, 1 ,4 , 3 , [5 + 2] 1, 2
#    -  -             ➀    -  -
#    2, 1 [4 + 3] ,  7,   1, 2
#            ➁
#    2, 1,    7   , 7     1, 2
#             -     -
#    [ 2  1 7  7 1 2 ] is palindrome
#    --------------------------------
#    Result : 2 operation
#  Test B
n = len(arr2)
#    [4   3   2   3   4   7]
#    ---------------------
#    [4 + 3   2   3   4   7]
#       ➀ //operation
#       7     2 + 3   4   7
#             -   -
#               ➁  //operation
#       7       5  +  4    7
#               -     -
#                  ➂ //operation
#       7          9       7
#    [7 9 7] is palindrome
#   -------------------------
#    Result = 3 operation
#  Test C
n = len(arr3)
#    [1, 2, 1]
#     -  -  -
#    1 2 1  is palindrome
#    Result = 0
#  Test D
n = len(arr4)
#    [1, 4, 1 , 5, 1]
#     -  -  -
#    1, [4 + 1] , 5   1
#          ➀
#    1,  5 , 5   1
#    Result = 1
#  Test E
n = len(arr5)
#    [1 , [2 + 3], 1]
#            ➀
#    Result = 1

if __name__ == "__main__": main()

Output

Array :   2  1  4  3  5  2  1  2
Result :  2
Array :   4  3  2  3  4  7
Result :  3
Array :   1  2  1
Result :  0
Array :   1  4  1  5  1
Result :  1
Array :   1  2  3  1
Result :  1
#  Ruby program for
#  Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
#  Display array elements
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

end

def minMergePalindrome(arr, n)
if (n <= 0)
return
end

#  Auxiliary variables
operation = 0
start = 0
last = n - 1
temp = Array.new(n) {0}
i = 0
#  Copy array element
while (i < n)
temp[i] = arr[i]
i += 1
end

while (start < last)
if (temp[start] == temp[last])
#  When boundary element is similar
#  Change boundary position
start += 1
last -= 1
elsif (temp[start] > temp[last])
#  When left side boundary element is
#  greater than right side boundary element.
#  Change last boundary -1 element
#  by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last]
#  Reduce last boundary position
last -= 1
#  increase operation
operation += 1
else

#  Change left side next element is
#  Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start]
#  Increase start boundary position
start += 1
#  Increase operation
operation += 1
end

end

print("\n Array : ")
self.printArray(arr, n)
print("\n Result : ", operation)
end

end

def main()
arr1 = [2, 1, 4, 3, 5, 2, 1, 2]
arr2 = [4, 3, 2, 3, 4, 7]
arr3 = [1, 2, 1]
arr4 = [1, 4, 1, 5, 1]
arr5 = [1, 2, 3, 1]
#  Test A
n = arr1.length
#    [2, 1 , 4 , 3 , 5 , 2, 1, 2]
#     -  -                  -  -
#    [Note boundary element 2, 1 is palindrome]
#    2, 1 ,4 , 3 , [5 + 2] 1, 2
#    -  -             ➀    -  -
#    2, 1 [4 + 3] ,  7,   1, 2
#            ➁
#    2, 1,    7   , 7     1, 2
#             -     -
#    [ 2  1 7  7 1 2 ] is palindrome
#    --------------------------------
#    Result : 2 operation
#  Test B
n = arr2.length
#    [4   3   2   3   4   7]
#    ---------------------
#    [4 + 3   2   3   4   7]
#       ➀ //operation
#       7     2 + 3   4   7
#             -   -
#               ➁  //operation
#       7       5  +  4    7
#               -     -
#                  ➂ //operation
#       7          9       7
#    [7 9 7] is palindrome
#   -------------------------
#    Result = 3 operation
#  Test C
n = arr3.length
#    [1, 2, 1]
#     -  -  -
#    1 2 1  is palindrome
#    Result = 0
#  Test D
n = arr4.length
#    [1, 4, 1 , 5, 1]
#     -  -  -
#    1, [4 + 1] , 5   1
#          ➀
#    1,  5 , 5   1
#    Result = 1
#  Test E
n = arr5.length
#    [1 , [2 + 3], 1]
#            ➀
#    Result = 1
end

main()

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
// Scala program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation()
{
// Display array elements
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
def minMergePalindrome(arr: Array[Int], n: Int): Unit = {
if (n <= 0)
{
return;
}
// Auxiliary variables
var operation: Int = 0;
var start: Int = 0;
var last: Int = n - 1;
var temp: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 0;
// Copy array element
while (i < n)
{
temp(i) = arr(i);
i += 1;
}
while (start < last)
{
if (temp(start) == temp(last))
{
// When boundary element is similar
// Change boundary position
start += 1;
last -= 1;
}
else if (temp(start) > temp(last))
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp(last - 1) = temp(last - 1) + temp(last);
// Reduce last boundary position
last -= 1;
// increase operation
operation += 1;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp(start + 1) = temp(start + 1) + temp(start);
// Increase start boundary position
start += 1;
// Increase operation
operation += 1;
}
}
print("\n Array : ");
printArray(arr, n);
print("\n Result : " + operation);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PalindromeOperation = new PalindromeOperation();
var arr1: Array[Int] = Array(2, 1, 4, 3, 5, 2, 1, 2);
var arr2: Array[Int] = Array(4, 3, 2, 3, 4, 7);
var arr3: Array[Int] = Array(1, 2, 1);
var arr4: Array[Int] = Array(1, 4, 1, 5, 1);
var arr5: Array[Int] = Array(1, 2, 3, 1);
// Test A
var n: Int = arr1.length;
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = arr2.length;
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.length;
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.length;
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.length;
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1
import Foundation;
// Swift 4 program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
{
// Display array elements
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
func minMergePalindrome(_ arr: [Int], _ n: Int)
{
if (n <= 0)
{
return;
}
// Auxiliary variables
var operation: Int = 0;
var start: Int = 0;
var last: Int = n - 1;
var temp: [Int] = Array(repeating: 0, count: n);
var i: Int = 0;
// Copy array element
while (i < n)
{
temp[i] = arr[i];
i += 1;
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start += 1;
last -= 1;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last -= 1;
// increase operation
operation += 1;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start += 1;
// Increase operation
operation += 1;
}
}
print("\n Array : ", terminator: "");
self.printArray(arr, n);
print("\n Result : ", operation, terminator: "");
}
}
func main()
{
let arr1: [Int] = [2, 1, 4, 3, 5, 2, 1, 2];
let arr2: [Int] = [4, 3, 2, 3, 4, 7];
let arr3: [Int] = [1, 2, 1];
let arr4: [Int] = [1, 4, 1, 5, 1];
let arr5: [Int] = [1, 2, 3, 1];
// Test A
var n: Int = arr1.count;
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = arr2.count;
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.count;
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.count;
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.count;
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}
main();

Output

Array :   2  1  4  3  5  2  1  2
Result :  2
Array :   4  3  2  3  4  7
Result :  3
Array :   1  2  1
Result :  0
Array :   1  4  1  5  1
Result :  1
Array :   1  2  3  1
Result :  1
// Kotlin program for
// Find minimum number of merge operations to make an array palindrome
class PalindromeOperation
{
// Display array elements
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
fun minMergePalindrome(arr: Array < Int > , n: Int): Unit
{
if (n <= 0)
{
return;
}
// Auxiliary variables
var operation: Int = 0;
var start: Int = 0;
var last: Int = n - 1;
val temp: Array < Int > = Array(n)
{
0
};
var i: Int = 0;
// Copy array element
while (i < n)
{
temp[i] = arr[i];
i += 1;
}
while (start < last)
{
if (temp[start] == temp[last])
{
// When boundary element is similar
// Change boundary position
start += 1;
last -= 1;
}
else if (temp[start] > temp[last])
{
// When left side boundary element is
// greater than right side boundary element.
// Change last boundary -1 element
// by sum of last two boundary element.
temp[last - 1] = temp[last - 1] + temp[last];
// Reduce last boundary position
last -= 1;
// increase operation
operation += 1;
}
else
{
// Change left side next element is
// Sum of two starting boundary element.
temp[start + 1] = temp[start + 1] + temp[start];
// Increase start boundary position
start += 1;
// Increase operation
operation += 1;
}
}
print("\n Array : ");
this.printArray(arr, n);
print("\n Result : " + operation);
}
}
fun main(args: Array < String > ): Unit
{
val arr1: Array < Int > = arrayOf(2, 1, 4, 3, 5, 2, 1, 2);
val arr2: Array < Int > = arrayOf(4, 3, 2, 3, 4, 7);
val arr3: Array < Int > = arrayOf(1, 2, 1);
val arr4: Array < Int > = arrayOf(1, 4, 1, 5, 1);
val arr5: Array < Int > = arrayOf(1, 2, 3, 1);
// Test A
var n: Int = arr1.count();
/*
[2, 1 , 4 , 3 , 5 , 2, 1, 2]
-  -                  -  -
[Note boundary element 2, 1 is palindrome]

2, 1 ,4 , 3 , [5 + 2] 1, 2
-  -             ➀    -  -
2, 1 [4 + 3] ,  7,   1, 2
➁
2, 1,    7   , 7     1, 2
-     -
[ 2  1 7  7 1 2 ] is palindrome
--------------------------------
Result : 2 operation
*/
// Test B
n = arr2.count();
/*
[4   3   2   3   4   7]
---------------------
[4 + 3   2   3   4   7]
➀ //operation
7     2 + 3   4   7
-   -
➁  //operation
7       5  +  4    7
-     -
➂ //operation
7          9       7

[7 9 7] is palindrome
-------------------------
Result = 3 operation
*/
// Test C
n = arr3.count();
/*
[1, 2, 1]
-  -  -
1 2 1  is palindrome
Result = 0
*/
// Test D
n = arr4.count();
/*
[1, 4, 1 , 5, 1]
-  -  -

1, [4 + 1] , 5   1
➀
1,  5 , 5   1

Result = 1
*/
// Test E
n = arr5.count();
/*
[1 , [2 + 3], 1]
➀
Result = 1
*/
}

Output

Array :  2 1 4 3 5 2 1 2
Result : 2
Array :  4 3 2 3 4 7
Result : 3
Array :  1 2 1
Result : 0
Array :  1 4 1 5 1
Result : 1
Array :  1 2 3 1
Result : 1

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post