33. Minimum merge to make an array palindrome

33. Minimum merge to make an array palindrome

Problem link :- click here
Approach ---> Two pointer

// APPROACH ----->  TWO POINTER
package programs;

import java.util.*;

public class Array__33
{

	/*
	    we can do only one operation to make the given array palindrome 
	    that is merging (we can replace two consecutive elements by their sum, 2 elements becomes 1)
	*/
	static int minMerge(int arr[], int n)
	{
		//since we are checking whether the array is plaindrome 
		//the last and first element must be the same.
		int i, j;
		i = 0; 
		j = n-1;
		
		int merges = 0;
		while(i<j)
		{
			if(arr[i] == arr[j])
			{
				i++;
				j--;
			}
			else if(arr[i] < arr[j])
			{
				/*
				     since arr[i] is less than arr[j] we must merge the elements
				      arr[i] and arr[i+1]   to arr[i+1]
				      and move one step right or else comparision is done between the same two elements
				 */
				arr[i+1] = arr[i] + arr[i+1];
				i++;
				merges++;
			}
			else
			{
				/*
				    here arr[j] is less than arr[i] we must merge the elements 
				    arr[j] and arr[j-1]  to arr[j-1]
				    we should merge j with its left element because its right element 
				              is already verified and it is in palindrome
				    and we should move one step left as mentioned above 
		                */
				arr[j-1] = arr[j] + arr[j-1];
				j--;
				merges++;
			}
		}
		
		return merges;
	}
	
	public static void main(String[] args)
	{
		int i, n, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given Array : ");
		printArray(array);
		
		ans = minMerge(array, n);
		System.out.println("\n\nMinimum merge required to make the array palindrome : " + ans);

	}

	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)