Skip to main content

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)
	{
		PalindromeOperation task = new PalindromeOperation();
		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

		*/
		task.minMergePalindrome(arr1, n);
		// 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
		*/
		task.minMergePalindrome(arr2, n);
		// Test C
		n = arr3.length;
		/*
		        
		    [1, 2, 1]
		     -  -  - 
		    1 2 1  is palindrome
		    Result = 0
		*/
		task.minMergePalindrome(arr3, n);
		// Test D
		n = arr4.length;
		/*
		    
		    [1, 4, 1 , 5, 1]
		     -  -  - 
		    
		    1, [4 + 1] , 5   1
		          ➀  
		    1,  5 , 5   1
		       
		    Result = 1
		*/
		task.minMergePalindrome(arr4, n);
		// Test E
		n = arr5.length;
		/*
		    
		    [1 , [2 + 3], 1]
		            ➀ 

		    Result = 1
		*/
		task.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
// Include header file
#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()
{
	PalindromeOperation *task = new PalindromeOperation();
	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
	*/
	task->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
	*/
	task->minMergePalindrome(arr2, n);
	// Test C
	n = sizeof(arr3) / sizeof(arr3[0]);
	/*
	    [1, 2, 1]
	     -  -  - 
	    1 2 1  is palindrome
	    Result = 0
	*/
	task->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
	*/
	task->minMergePalindrome(arr4, n);
	// Test E
	n = sizeof(arr5) / sizeof(arr5[0]);
	/*
	    [1 , [2 + 3], 1]
	            ➀ 
	    Result = 1
	*/
	task->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
// 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)
	{
		PalindromeOperation task = new PalindromeOperation();
		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
		*/
		task.minMergePalindrome(arr1, n);
		// 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
		*/
		task.minMergePalindrome(arr2, n);
		// Test C
		n = arr3.Length;
		/*
		    [1, 2, 1]
		     -  -  - 
		    1 2 1  is palindrome
		    Result = 0
		*/
		task.minMergePalindrome(arr3, n);
		// Test D
		n = arr4.Length;
		/*
		    [1, 4, 1 , 5, 1]
		     -  -  - 
		    
		    1, [4 + 1] , 5   1
		          ➀  
		    1,  5 , 5   1
		       
		    Result = 1
		*/
		task.minMergePalindrome(arr4, n);
		// Test E
		n = arr5.Length;
		/*
		    [1 , [2 + 3], 1]
		            ➀ 
		    Result = 1
		*/
		task.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
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()
{
	$task = new PalindromeOperation();
	$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
	*/
	$task->minMergePalindrome($arr1, $n);
	// 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
	*/
	$task->minMergePalindrome($arr2, $n);
	// Test C
	$n = count($arr3);
	/*
	    [1, 2, 1]
	     -  -  - 
	    1 2 1  is palindrome
	    Result = 0
	*/
	$task->minMergePalindrome($arr3, $n);
	// Test D
	$n = count($arr4);
	/*
	    [1, 4, 1 , 5, 1]
	     -  -  - 
	    
	    1, [4 + 1] , 5   1
	          ➀  
	    1,  5 , 5   1
	       
	    Result = 1
	*/
	$task->minMergePalindrome($arr4, $n);
	// Test E
	$n = count($arr5);
	/*
	    [1 , [2 + 3], 1]
	            ➀ 
	    Result = 1
	*/
	$task->minMergePalindrome($arr5, $n);
}
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 task = new PalindromeOperation();
	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
	*/
	task.minMergePalindrome(arr1, n);
	// 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
	*/
	task.minMergePalindrome(arr2, n);
	// Test C
	n = arr3.length;
	/*
	    [1, 2, 1]
	     -  -  - 
	    1 2 1  is palindrome
	    Result = 0
	*/
	task.minMergePalindrome(arr3, n);
	// Test D
	n = arr4.length;
	/*
	    [1, 4, 1 , 5, 1]
	     -  -  - 
	    
	    1, [4 + 1] , 5   1
	          ➀  
	    1,  5 , 5   1
	       
	    Result = 1
	*/
	task.minMergePalindrome(arr4, n);
	// Test E
	n = arr5.length;
	/*
	    [1 , [2 + 3], 1]
	            ➀ 
	    Result = 1
	*/
	task.minMergePalindrome(arr5, n);
}
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() :
	task = PalindromeOperation()
	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
	task.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
	task.minMergePalindrome(arr2, n)
	#  Test C
	n = len(arr3)
	#    [1, 2, 1]
	#     -  -  - 
	#    1 2 1  is palindrome
	#    Result = 0
	task.minMergePalindrome(arr3, n)
	#  Test D
	n = len(arr4)
	#    [1, 4, 1 , 5, 1]
	#     -  -  - 
	#    1, [4 + 1] , 5   1
	#          ➀  
	#    1,  5 , 5   1
	#    Result = 1
	task.minMergePalindrome(arr4, n)
	#  Test E
	n = len(arr5)
	#    [1 , [2 + 3], 1]
	#            ➀ 
	#    Result = 1
	task.minMergePalindrome(arr5, n)

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() 
	task = PalindromeOperation.new()
	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
	task.minMergePalindrome(arr1, n)
	#  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
	task.minMergePalindrome(arr2, n)
	#  Test C
	n = arr3.length
	#    [1, 2, 1]
	#     -  -  - 
	#    1 2 1  is palindrome
	#    Result = 0
	task.minMergePalindrome(arr3, n)
	#  Test D
	n = arr4.length
	#    [1, 4, 1 , 5, 1]
	#     -  -  - 
	#    1, [4 + 1] , 5   1
	#          ➀  
	#    1,  5 , 5   1
	#    Result = 1
	task.minMergePalindrome(arr4, n)
	#  Test E
	n = arr5.length
	#    [1 , [2 + 3], 1]
	#            ➀ 
	#    Result = 1
	task.minMergePalindrome(arr5, n)
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
		*/
		task.minMergePalindrome(arr1, n);
		// 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
		*/
		task.minMergePalindrome(arr2, n);
		// Test C
		n = arr3.length;
		/*
		    [1, 2, 1]
		     -  -  - 
		    1 2 1  is palindrome
		    Result = 0
		*/
		task.minMergePalindrome(arr3, n);
		// Test D
		n = arr4.length;
		/*
		    [1, 4, 1 , 5, 1]
		     -  -  - 
		    
		    1, [4 + 1] , 5   1
		          ➀  
		    1,  5 , 5   1
		       
		    Result = 1
		*/
		task.minMergePalindrome(arr4, n);
		// Test E
		n = arr5.length;
		/*
		    [1 , [2 + 3], 1]
		            ➀ 
		    Result = 1
		*/
		task.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
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 task: PalindromeOperation = PalindromeOperation();
	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
	*/
	task.minMergePalindrome(arr1, n);
	// 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
	*/
	task.minMergePalindrome(arr2, n);
	// Test C
	n = arr3.count;
	/*
	    [1, 2, 1]
	     -  -  - 
	    1 2 1  is palindrome
	    Result = 0
	*/
	task.minMergePalindrome(arr3, n);
	// Test D
	n = arr4.count;
	/*
	    [1, 4, 1 , 5, 1]
	     -  -  - 
	    
	    1, [4 + 1] , 5   1
	          ➀  
	    1,  5 , 5   1
	       
	    Result = 1
	*/
	task.minMergePalindrome(arr4, n);
	// Test E
	n = arr5.count;
	/*
	    [1 , [2 + 3], 1]
	            ➀ 
	    Result = 1
	*/
	task.minMergePalindrome(arr5, n);
}
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 task: PalindromeOperation = PalindromeOperation();
	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
	*/
	task.minMergePalindrome(arr1, n);
	// 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
	*/
	task.minMergePalindrome(arr2, n);
	// Test C
	n = arr3.count();
	/*
	    [1, 2, 1]
	     -  -  - 
	    1 2 1  is palindrome
	    Result = 0
	*/
	task.minMergePalindrome(arr3, n);
	// Test D
	n = arr4.count();
	/*
	    [1, 4, 1 , 5, 1]
	     -  -  - 
	    
	    1, [4 + 1] , 5   1
	          ➀  
	    1,  5 , 5   1
	       
	    Result = 1
	*/
	task.minMergePalindrome(arr4, n);
	// Test E
	n = arr5.count();
	/*
	    [1 , [2 + 3], 1]
	            ➀ 
	    Result = 1
	*/
	task.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
Last updated on by Kalkicode




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.

New Comment