Monthly Archives: May 2016

Find minimum number of merge operations to make an array palindrome

Find minimum number of merge operations to make an array palindrome

In this post we try to convert a given array into a palindrome by using minimum number of merge operations.

Find minimum number of merge operations to make an array palindrome

Given an array of positive integers. We need to make the given array a ‘Palindrome’.

A Palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.Only allowed operation on array is merge. Here, Merging two adjacent elements means replacing them with their sum.

The task is to find minimum number of merge operations required to make given array a ‘Palindrome’.To make an array a palindromic we can simply apply merging operations n-1 times where n is the size of array (Note a single element array is always palindrome similar to single character string). In that case, size of array will be reduced to 1. But in this problem we are asked to do it in minimum number of operations.

Find minimum number of merge operations to make an array palindrome example

Input Array: { 5, 3, 4, 5 }
Output: 1
The given array can be merged and made into palindrome by adding 3 and 4.
Input Array: { 7, 8, 1, 3 }
Output: 3
The given array can be made a palindrome only by adding all the elements one by one.

 

Find minimum number of merge operations to make an array palindrome solution

We solve this problem iteratively using two pointers one pointing to the start and other pointing to the last element of the array.We keep a track of the merging operations done till now.

Let m(i, j) be minimum merging operations to make subarray arr[i..j] a palindrome.
If i == j answer is 0. We start i from 0 and j from n-1.

  1. If arr[i] == arr[j], then there is no need to do any merging operations . Answer in this case will be f(i+1, j-1).
  2. Else, we need to do merging operations. Following cases arise.
    1. If arr[i] > arr[j], then we should do merging operation at index j. We merge index j-1 and j, and update arr[j-1] = arr[j-1] + arr[j]. Our answer in this case will be 1 + f(i, j-1).
    2. For the case when arr[i] < arr[j], update arr[i+1] = arr[i+1] + arr[i]. Our answer in this case will be 1 + f(i+1, j).
  3. Our answer will be f(0, n-1), where n is size of array arr[].

Find minimum number of merge operations to make an array palindrome solution code in c++:

#include <bits/stdc++.h>
using namespace std;

// 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, 3, 5, 8, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of minimum operations is "
         <<  FindMinOps(arr, n) << endl;
    return 0;
}

 Output:

Count of minimum operations is 1

Time Complexity: O(N)
Space Complexity:O(1)

Group even and odd numbers in a linked list

Group even and odd numbers in a linked list

Problem statement for segregating even and odd numbers in a linked list:

Given a singly linked list, you have to group the even numbers and the odd numbers. The even numbers’ group must be ahead the group of odd numbers. Also, each number in the groups must be in the same order as they appear in the list.

Grouping even and odd numbers in a linked list Example:

Consider a singly linked list:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant list should be
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Solution to group even and odd numbers of a linked list:

Method 1:

Algorithm to group even and odd numbers of a linked list:

  1. Place a pointer to the last node of the list.
  2. Traverse the list from the first node to the last node.
    1. If the data of traversed node is an even number, move to the next node.
    2. If data is an odd number, move the node to the end of the list.

Solution in C++ for groupping even and odd numbers of a linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to group even and
odd numbers in a linked list*/
void group_even_odd(node **head)
{
   if(*head == NULL)
   {
      cout<<"\nEmpty list.";
      exit(0);
   }
   
   node *last = *head;
   node *first_even_node = NULL;
   int n = 0;

   /*Loop finds the last node,
   the first even node and sets 
   n = total nodes-1*/
   while(last->next != NULL)
   {
      n++;
      if(first_even_node == NULL && (last->data) % 2 == 0)
         first_even_node = last;
      last = last->next;
   }
   
   node *prev = NULL;
   node *curr = *head;
   node *temp;
   int i;
   
   /*Loop traverses each node of list*/
   for(i=0 ; i<=n ; i++)
   {
      /*If data of node is odd*/
      if((curr->data)%2 != 0)
      {	
         temp = curr->next;
         
         /*If curr is not head node*/
         if(prev != NULL)
            prev->next = curr->next;
         
         /*Moving curr to end of list*/
         curr->next = NULL;
         last->next = curr;
         last = curr;
         curr = temp;
      }
      
      /*If node data is even*/
      else
      {
         /*Moving to next node*/
         prev = curr;
         curr = curr->next;
      }
   }
   
   /*Updating head*/
   *head = first_even_node;
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 7);
  InsFront(&head, 4);
  InsFront(&head, 6);
  InsFront(&head, 8);
  InsFront(&head, 3);
  InsFront(&head, 9);
  InsFront(&head, 2);
  InsFront(&head, 1);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to group
  even and odd nodes of list*/
  group_even_odd(&head);
  
  cout<<"\nResultant Linked list is:\n";
  printList(head);
 
  return 0;
}

Output:

Created Linked list is:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant Linked list is:
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Time Complexity of groupping even and odd numbers of a linked list: O(N)
where N is the total number of nodes in the given linked list.


Method 2:

Algorithm to group even and odd numbers of a linked list:

  1. Traverse each node of linked list.
    1. If node data is an even number, move to next node.
    2. If node is an odd number, move it to another list which contains all odd nodes.
  2. Repeat for all nodes in list.
  3. Combine the two lists.

Solution in C++ for groupping even and odd numbers of a linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes at end of Linked List*/
void InsEnd(node **head, node **last, int data)
{
    node *temp = new node;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if((*head) == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}
 
/*Function to group even and
odd numbers in a linked list*/
void group_even_odd(node **head)
{
   if(*head == NULL)
   {
      cout<<"\nEmpty list.";
      exit(0);
   }
   
   node *last = NULL;
   node *curr = *head;
   node *odd_list_head = NULL;
   node *prev = NULL;
   node *temp;
   
   /*Traverse list*/
   while(curr != NULL)
   {
      /*If node has odd value*/
      if((curr->data)%2 != 0)
      {
         /*Insert into another list*/
         InsEnd(&odd_list_head,&last,curr->data);
         curr = curr->next;
      }
      
      /*If node has even value*/
      else
         /*Break loop. curr points
         to first even node*/
         break;
   }
   
   /*If list has no even node*/
   if(curr == NULL)
      return;
   
   /*head points to first even node*/
   *head = curr;
   
   /*Traverse remaining list*/
   while(curr != NULL)
   {		
      /*If node has odd value*/
      if((curr->data)%2 != 0)
      {
         /*Insert into another list*/
         InsEnd(&odd_list_head,&last,curr->data);
         
         /*Delete odd node from list*/
         temp = curr;
         prev->next = curr->next;
         delete temp;
         curr = prev->next;
      }
      
      /*If node has even value*/
      else
      {
         /*Move to respective next nodes*/
         prev = curr;
         curr = curr->next;
      }
   }
   
   /*Combine even and odd lists*/
   prev->next = odd_list_head;
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL,*last = NULL;
  InsEnd(&head, &last,1);
  InsEnd(&head, &last,2); 
  InsEnd(&head, &last,9);
  InsEnd(&head, &last,3);
  InsEnd(&head, &last,8);
  InsEnd(&head, &last,6);
  InsEnd(&head, &last,4);
  InsEnd(&head, &last,7);

  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to group
  even and odd nodes of list*/
  group_even_odd(&head);
  
  cout<<"\nResultant Linked list is:\n";
  printList(head);
 
  return 0;
}

Output:

Created Linked list is:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant Linked list is:
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Time Complexity of grouping even and odd numbers of a linked list: O(N)
where N is the total number of nodes in the given linked list.