Rearrangement

Page 1

Program -8 :Search an element in a sorted and rotated array

Ans - An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

/* Java program to search an element

in a sorted and pivoted array*/

class Main

{

/* Searches an element key in a

pivoted sorted array arrp[]

of size n */

static int pivotedBinarySearch(int arr[], int n, int key)

{

int pivot = findPivot(arr, 0, n-1);

// If we didn't find a pivot, then

// array is not rotated at all

if (pivot == -1)

return binarySearch(arr, 0, n-1, key);

// If we found a pivot, then first

// compare with pivot and then

// search in two subarrays around pivot

if (arr[pivot] == key)

return pivot;

if (arr[0] <= key)

return binarySearch(arr, 0, pivot-1, key);

return binarySearch(arr, pivot+1, n-1, key);

}

/* Function to get pivot. For array

3, 4, 5, 6, 1, 2 it returns

3 (index of 6) */

static int findPivot(int arr[], int low, int high)

{

// base cases

if (high < low)

return -1;

if (high == low)

return low;

/* low + (high - low)/2; */

int mid = (low + high)/2;

if (mid < high && arr[mid] > arr[mid + 1])

return mid;

if (mid > low && arr[mid] < arr[mid - 1])

return (mid-1);

if (arr[low] >= arr[mid])

return findPivot(arr, low, mid-1);

return findPivot(arr, mid + 1, high);

}

/* Standard Binary Search function */

static int binarySearch(int arr[], int low, int high, int key)

{

if (high < low)

return -1;

/* low + (high - low)/2; */

int mid = (low + high)/2;

if (key == arr[mid])

return mid;

if (key > arr[mid])

return binarySearch(arr, (mid + 1), high, key);

return binarySearch(arr, low, (mid -1), key);

}

// main function

public static void main(String args[])

{

// Let us search 3 in below array

int arr1[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};

int n = arr1.length;

int key = 3;

System.out.println("Index of the element is: " + pivotedBinarySearch(arr1, n, key));

}

}

Program-9: Given a sorted and rotated array, find if there is a pair with a given sum

Ans: Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16

Output: true

There is a pair (6, 10) with sum 16

Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35

Output: true

There is a pair (26, 9) with sum 35

bool pairInSortedRotated(int arr[], int n, int x)

{

// Find the pivot element

int i;

for (i=0; i<n-1; i++)

if (arr[i] > arr[i+1])

break;

int l = (i+1)%n; // l is now index of minimum element

int r = i; // r is now index of maximum element

// Keep moving either l or r till they meet

while (l != r)

{

// If we find a pair with sum x, we return true

if (arr[l] + arr[r] == x)

return true;

// If current pair sum is less, move to the higher sum

if (arr[l] + arr[r] < x)

l = (l + 1)%n;

else // Move to the lower sum side

r = (n + r - 1)%n;

}

return false;

}

Program-10 : Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed

Ans - Input: arr[] = {1, 20, 2, 10}

Output: 72

We can 72 by rotating array twice.

{2, 10, 1, 20}

20*3 + 1*2 + 10*1 + 2*0 = 72

Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Output: 330

We can 330 by rotating array 9 times.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

0*1 + 1*2 + 2*3 ... 9*10 = 330

Let us calculate initial value of i*arr[i] with no rotation

R0 = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]

After 1 rotation arr[n-1], becomes first element of array, arr[0] becomes second element, arr[1] becomes third element and so on.

R1 = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2]

R1 - R0 = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1]

After 2 rotations arr[n-2], becomes first element of array, arr[n-1] becomes second element, arr[0] becomes third element and so on.

R2 = 0*arr[n-2] + 1*arr[n-1] +...+ (n?1)*arr[n-3]

R2 - R1 = arr[0] + arr[1] + ... + arr[n-3] - (n-1)*arr[n-2] + arr[n-1]

If we take a closer look at above values, we can observe below pattern

Rj - Rj-1 = arrSum - n * arr[n-j]

Where arrSum is sum of all array elements, i.e.,

arrSum = ? arr[i] i<=0<=n-1

static int maxSum()

{

// Find array sum and i*arr[i] with no rotation

int arrSum = 0; // Stores sum of arr[i]

int currVal = 0; // Stores sum of i*arr[i]

for (int i=0; i<arr.length; i++)

{

arrSum = arrSum + arr[i];

currVal = currVal+(i*arr[i]);

}

// Initialize result as 0 rotation sum

int maxVal = currVal;

// Try all rotations one by one and find

// the maximum rotation sum.

for (int j=1; j<arr.length; j++)

{

currVal = currVal + arrSum-arr.length*arr[arr.length-j];

if (currVal > maxVal)

maxVal = currVal;

}

// Return result

return maxVal;

}

Program 11- Rearrange positive and negative numbers in O(n) time and O(1) extra space

Ans - For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

static void rearrange(int arr[], int n)

{

// The following few lines are similar to partition

// process of QuickSort. The idea is to consider 0

// as pivot and divide the array around it.

int i = -1, temp = 0;

for (int j = 0; j < n; j++)

{

if (arr[j] < 0)

{

i++;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

// Now all positive numbers are at end and negative numbers at

// the beginning of array. Initialize indexes for starting point

// of positive and negative numbers to be swapped

int pos = i+1, neg = 0;

// Increment the negative index by 2 and positive index by 1, i.e.,

// swap every alternate negative number with next positive number

while (pos < n && neg < pos && arr[neg] < 0)

{

temp = arr[neg];

arr[neg] = arr[pos];

arr[pos] = temp;

pos++;

neg += 2;

}

}

Program 12- Sort an array according to absolute difference with given value

Ans-

Input : arr[] : x = 7, arr[] = {10, 5, 3, 9, 2}

Output : arr[] = {5, 9, 10, 3, 2}

Explanation:

7 - 10 = 3(abs)

7 - 5 = 2

7 - 3 = 4

7 - 9 = 2(abs)

7 - 2 = 5

So according to the difference with X,

elements are arranged as 5, 9, 10, 3, 2.

// C++ program to sort an array according absolute

// difference with x.

#include<bits/stdc++.h>

using namespace std;

// Function to sort an array according absolute

// difference with x.

void rearrange(int arr[], int n, int x)

{

multimap<int, int> m;

// Store values in a map with the difference

// with X as key

for (int i = 0 ; i < n; i++)

m.insert(make_pair(abs(x-arr[i]),arr[i]));

// Update the values of array

int i = 0;

for (auto it = m.begin(); it != m.end(); it++)

arr[i++] = (*it).second ;

}

// Function to print the array

void printArray(int arr[] , int n)

{

for (int i = 0 ; i < n; i++)

cout << arr[i] << " ";

}

// Driver code

int main()

{

int arr[] = {10, 5, 3, 9 ,2};

int n = sizeof(arr)/sizeof(arr[0]);

int x = 7;

rearrange(arr, n, x);

printArray(arr, n);

return 0;

}

Program-13 Three way partitioning of an array around a given range

Ans -

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}

lowVal = 14, highVal = 20

Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}

public static void threeWayPartition(int[] arr, int lowVal, int highVal)

{

int n = arr.length;

// Initialize ext available positions for

// smaller (than range) and greater lements

int start = 0, end = n-1;

// Traverse elements from left

for(int i = 0; i < end;)

{

// If current element is smaller than

// range, put it on next available smaller

// position.

if(arr[i] < lowVal)

{

int temp = arr[start];

arr[start] = arr[i];

arr[i] = temp;

start++;

i++;

}

// If current element is greater than

// range, put it on next available greater

// position.

else if(arr[i] > highVal)

{

int temp = arr[end];

arr[end] = arr[i];

arr[i] = temp;

end--;

}

else

i++;

}

}

Program-14 Rearrange an array in maximum minimum form

Ans - Input : arr[] = {1, 2, 3, 4, 5, 6, 7}

Output : arr[] = {7, 1, 6, 2, 5, 3, 4}

static void rearrange(int[] arr, int n)

{

// Auxiliary array to hold modified array

int temp[] = new int[n];

// Indexes of smallest and largest elements

// from remaining array.

int small=0, large=n-1;

// To indicate whether we need to copy rmaining

// largest or remaining smallest at next position

boolean flag = true;

// Store result in temp[]

for (int i=0; i<n; i++)

{

if (flag)

temp[i] = arr[large--];

else

temp[i] = arr[small++];

flag = !flag;

}

// Copy temp[] to arr[]

arr = temp.clone();

}

Program-15 Rearrange an array in maximum minimum form | Set 2 (O(1) extra space)

Ans- Input : arr[] = {1, 2, 3, 4, 5, 6, 7}

Output : arr[] = {7, 1, 6, 2, 5, 3, 4}

void rearrange(int arr[], int n)

{

// initialize index of first minimum and first

// maximum element

int max_idx = n-1 , min_idx = 0 ;

// store maximum element of array

int max_elem = arr[n-1] + 1 ;

// traverse array elements

for (int i=0; i < n ; i++)

{

// at even index : we have to put maximum element

if (i % 2 == 0)

{

arr[i] += (arr[max_idx] % max_elem ) * max_elem;

max_idx--;

}

// at odd index : we have to put minimum element

else

{

arr[i] += (arr[min_idx] % max_elem ) * max_elem;

min_idx++;

}

}

// array elements back to it's original form

for (int i = 0 ; i < n; i++)

arr[i] = arr[i] / max_elem ;

}

Program-16 Maximum Length Bitonic Subarray | Set 1 (O(n) tine and O(n) space)

Ans- A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.

static int bitonic(int arr[], int n)

{

int[] inc = new int[n]; // Length of increasing subarray ending

// at all indexes

int[] dec = new int[n]; // Length of decreasing subarray starting

// at all indexes

int max;

// Length of increasing sequence ending at first index is 1

inc[0] = 1;

// Length of increasing sequence starting at first index is 1

dec[n-1] = 1;

// Step 1) Construct increasing sequence array

for (int i = 1; i < n; i++)

inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;

// Step 2) Construct decreasing sequence array

for (int i = n-2; i >= 0; i--)

dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;

// Step 3) Find the length of maximum length bitonic sequence

max = inc[0] + dec[0] - 1;

for (int i = 1; i < n; i++)

if (inc[i] + dec[i] - 1 > max)

max = inc[i] + dec[i] - 1;

return max;

}

Program-17 Maximize sum of consecutive differences in a circular array

Ans- Input : arr[] = { 4, 2, 1, 8 }

Output : 18

Rearrange given array as : { 1, 8, 2, 4 }

Sum of difference between consecutive element

= |1 - 8| + |8 - 2| + |2 - 4| + |4 - 1|

= 7 + 6 + 2 + 3

= 18.

static int maxSum(int arr[], int n)

{

int sum = 0;

// Sorting the array.

Arrays.sort(arr);

// Subtracting a1, a2, a3,....., a(n/2)-1,

// an/2 twice and adding a(n/2)+1, a(n/2)+2,

// a(n/2)+3,....., an - 1, an twice.

for (int i = 0; i < n/2; i++)

{

sum -= (2 * arr[i]);

sum += (2 * arr[n - i - 1]);

}

return sum;

}

Program-18 Alternative Sorting

Ans- Input : arr[] = {7, 1, 2, 3, 4, 5, 6}

Output : 7 1 6 2 5 3 4

static void alternateSort(int arr[], int n)

{

Arrays.sort(arr);

// Printing the last element of array

// first and then first element and then

// second last element and then second

// element and so on.

int i = 0, j = n-1;

while (i < j) {

System.out.print(arr[j--] + " ");

System.out.print(arr[i++] + " ");

}

// If the total element in array is odd

// then print the last middle element.

if (n % 2 != 0)

System.out.print(arr[i]);

}

Program-19 Segregate 0s and 1s in an array

Ans- Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]

Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

static void segregate0and1(int arr[], int n)

{

int count = 0; // counts the no of zeros in arr

for (int i = 0; i < n; i++) {

if (arr[i] == 0)

count++;

}

// loop fills the arr with 0 until count

for (int i = 0; i < count; i++)

arr[i] = 0;

// loop fills remaining arr space with 1

for (int i = count; i < n; i++)

arr[i] = 1;

}

Program-20 Segregate Even and Odd numbers

Ans- Input = {12, 34, 45, 9, 8, 90, 3}

Output = {12, 34, 8, 90, 45, 9, 3}

static void segregateEvenOdd(int arr[])

{

/* Initialize left and right indexes */

int left = 0, right = arr.length - 1;

while (left < right)

{

/* Increment left index while we see 0 at left */

while (arr[left]%2 == 0 && left < right)

left++;

/* Decrement right index while we see 1 at right */

while (arr[right]%2 == 1 && left < right)

right--;

if (left < right)

{

/* Swap arr[left] and arr[right]*/

int temp = arr[left];

arr[left] = arr[right];

arr[right] = temp;

left++;

right--;

}

}

}

Program-21 Replace every element with the greatest element on right side

Ans- {16, 17, 4, 3, 5, 2} - {17, 5, 5, 5, 2, -1}

static void nextGreatest(int arr[])

{

int size = arr.length;

// Initialize the next greatest element

int max_from_right = arr[size-1];

// The next greatest element for the rightmost

// element is always -1

arr[size-1] = -1;

// Replace all other elements with the next greatest

for (int i = size-2; i >= 0; i--)

{

// Store the current element (needed later for

// updating the next greatest element)

int temp = arr[i];

// Replace current element with the next greatest

arr[i] = max_from_right;

// Update the greatest element, if needed

if(max_from_right < temp)

max_from_right = temp;

}

}

Program-22 Find a sorted subsequence of size 3 in linear time

Ans- Input: arr[] = {12, 11, 10, 5, 6, 2, 30}

Output: 5, 6, 30

static void find3Numbers(int arr[])

{

int n = arr.length;

int max = n-1; //Index of maximum element from right side

int min = 0; //Index of minimum element from left side

int i;

// Create an array that will store index of a smaller

// element on left side. If there is no smaller element

// on left side, then smaller[i] will be -1.

int[] smaller = new int[n];

smaller[0] = -1; // first entry will always be -1

for (i = 1; i < n; i++)

{

if (arr[i] <= arr[min])

{

min = i;

smaller[i] = -1;

}

else

smaller[i] = min;

}

// Create another array that will store index of a

// greater element on right side. If there is no greater

// element on right side, then greater[i] will be -1.

int[] greater = new int[n];

greater[n-1] = -1; // last entry will always be -1

for (i = n-2; i >= 0; i--)

{

if (arr[i] >= arr[max])

{

max = i;

greater[i] = -1;

}

else

greater[i] = max;

}

// Now find a number which has both a greater number

// on right side and smaller number on left side

for (i = 0; i < n; i++)

{

if (smaller[i] != -1 && greater[i] != -1)

{

System.out.print(arr[smaller[i]]+" "+

arr[i]+" "+ arr[greater[i]]);

return;

}

}

// If we reach number, then there are no such 3 numbers

System.out.println("No such triplet found");

return;

}

Program-23 Largest subarray with equal number of 0s and 1s

Ans- Input: arr[] = {1, 0, 1, 1, 1, 0, 0}

Output: 1 to 6 (Starting and Ending indexes of output subarray)

int maxLen(int arr[], int n)

{

// Creates an empty hashMap hM

HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

int sum = 0; // Initialize sum of elements

int max_len = 0; // Initialize result

int ending_index = -1;

int start_index = 0;

for (int i = 0; i < n; i++)

{

arr[i] = (arr[i] == 0) ? -1 : 1;

}

// Traverse through the given array

for (int i = 0; i < n; i++)

{

// Add current element to sum

sum += arr[i];

// To handle sum=0 at last index

if (sum == 0)

{

max_len = i + 1;

ending_index = i;

}

// If this sum is seen before, then update max_len

// if required

if (hM.containsKey(sum))

{

if (max_len < i - hM.get(sum + n))

{

max_len = i - hM.get(sum + n);

ending_index = i;

}

}

else // Else put this sum in hash table

hM.put(sum + n, i);

}

for (int i = 0; i < n; i++)

{

arr[i] = (arr[i] == -1) ? 0 : 1;

}

int end = ending_index - max_len + 1;

System.out.println(end + " to " + ending_index);

return max_len;

}

Program-24 Sort elements by frequency

Ans- {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

Following is detailed algorithm.

1) Create a BST and while creating BST maintain the count i,e frequency of each coming element in same BST. This step may take O(nLogn) time if a self balancing BST is used.

2) Do Inorder traversal of BST and store every element and count of each element in an auxiliary array. Let us call the auxiliary array as ‘count[]’. Note that every element of this array is element and frequency pair. This step takes O(n) time.

3) Sort ‘count[]’ according to frequency of the elements. This step takes O(nLohn) time if a O(nLogn) sorting algorithm is used.

4) Traverse through the sorted array ‘count[]’. For each element x, print it ‘freq’ times where ‘freq’ is frequency of x. This step takes O(n) time

Program-25 Merge k sorted arrays

Ans- Input: k = 3, n = 4

arr[][] = { {1, 3, 5, 7},

{2, 4, 6, 8},

{0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11

1. Create an output array of size n*k.

2. Create a min heap of size k and insert 1st element in all the arrays into a the heap

3. Repeat following steps n*k times.

a) Get minimum element from heap (minimum is always at root) and store it in output array.

b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Program-26 Sort an array according to the order defined by another array

Ans- Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}

A2[] = {2, 1, 8, 3}

Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}

/* A Binary Search based function to find index of FIRST occurrence

of x in arr[]. If x is not present, then it returns -1 */

int first(int arr[], int low, int high, int x, int n)

{

if (high >= low)

{

int mid = low + (high-low)/2; /* (low + high)/2; */

if ((mid == 0 || x > arr[mid-1]) && arr[mid] == x)

return mid;

if (x > arr[mid])

return first(arr, (mid + 1), high, x, n);

return first(arr, low, (mid -1), x, n);

}

return -1;

}

// Sort A1[0..m-1] according to the order defined by A2[0..n-1].

void sortAccording(int A1[], int A2[], int m, int n)

{

// The temp array is used to store a copy of A1[] and visited[]

// is used mark the visited elements in temp[].

int temp[m], visited[m];

for (int i=0; i<m; i++)

{

temp[i] = A1[i];

visited[i] = 0;

}

// Sort elements in temp

sort(temp, temp + m);

int ind = 0; // for index of output which is sorted A1[]

// Consider all elements of A2[], find them in temp[]

// and copy to A1[] in order.

for (int i=0; i<n; i++)

{

// Find index of the first occurrence of A2[i] in temp

int f = first(temp, 0, m-1, A2[i], m);

// If not present, no need to proceed

if (f == -1) continue;

// Copy all occurrences of A2[i] to A1[]

for (int j = f; (j<m && temp[j]==A2[i]); j++)

{

A1[ind++] = temp[j];

visited[j] = 1;

}

}

// Now copy all items of temp[] which are not present in A2[]

for (int i=0; i<m; i++)

if (visited[i] == 0)

A1[ind++] = temp[i];

}

Program-27 Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array

Ans- Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}

Output: Index 9

static int maxOnesIndex(int arr[], int n)

{

int max_count = 0; // for maximum number of 1 around a zero

int max_index=0; // for storing result

int prev_zero = -1; // index of previous zero

int prev_prev_zero = -1; // index of previous to previous zero

// Traverse the input array

for (int curr=0; curr<n; ++curr)

{

// If current element is 0, then calculate the difference

// between curr and prev_prev_zero

if (arr[curr] == 0)

{

// Update result if count of 1s around prev_zero is more

if (curr - prev_prev_zero > max_count)

{

max_count = curr - prev_prev_zero;

max_index = prev_zero;

}

// Update for next iteration

prev_prev_zero = prev_zero;

prev_zero = curr;

}

}

// Check for the last encountered zero

if (n-prev_prev_zero > max_count)

max_index = prev_zero;

return max_index;

}

Program-28 Generate all possible sorted arrays from alternate elements of two given sorted arrays

Ans- For Example

A = {10, 15, 25}

B = {1, 5, 20, 30}

The resulting arrays are:

10 20

10 20 25 30

10 30

15 20

15 20 25 30

15 30

25 30

void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n,

int len, boolean flag)

{

if (flag) // Include valid element from A

{

// Print output if there is at least one 'B' in output array 'C'

if (len != 0)

printArr(C, len + 1);

// Recur for all elements of A after current index

for (int k = i; k < m; k++)

{

if (len == 0)

{

/* this block works for the very first call to include

the first element in the output array */

C[len] = A[k];

// don't increment lem as B is included yet

generateUtil(A, B, C, k + 1, j, m, n, len, !flag);

}

/* include valid element from A and recur */

else if (A[k] > C[len])

{

C[len + 1] = A[k];

generateUtil(A, B, C, k + 1, j, m, n, len + 1, !flag);

}

}

}

/* Include valid element from B and recur */

else

{

for (int l = j; l < n; l++)

{

if (B[l] > C[len])

{

C[len + 1] = B[l];

generateUtil(A, B, C, i, l + 1, m, n, len + 1, !flag);

}

}

}

}

/* Wrapper function */

void generate(int A[], int B[], int m, int n)

{

int C[] = new int[m + n];

/* output array */

generateUtil(A, B, C, 0, 0, m, n, 0, true);

}

Program-29 Minimum number of swaps required for arranging pairs adjacent to each other

Ans- Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

1) If first and second elements are pair, then simply recur

for remaining n-1 pairs and return the value returned by

recursive call.

2) If first and second are NOT pair, then there are two ways to

arrange. So try both of them return the minimum of two.

a) Swap second with pair of first and recur for n-1 elements.

Let the value returned by recursive call be 'a'.

b) Revert the changes made by previous step.

c) Swap first with pair of second and recur for n-1 elements.

Let the value returned by recursive call be 'b'.

d) Revert the changes made by previous step before returning

control to parent call.

e) Return 1 + min(a, b)