in Algorithm Challenges retagged by
1,624 views
2 votes
2 votes
Given an array with possible repeating elements you have to rearrange such that elements are alternatively decreasing and increasing (strict increase/decrease). For example, suppose the given array is 1 1 2 3 4 5 one possible answer would be 2 1 3 1 5 4.
Assumption: Solution do exist for any given input.
Hint: Try to avoid sorting.
in Algorithm Challenges retagged by
by
1.6k views

4 Comments

edited by

sir,,,using sorting we can not find the solution ????

i tried u just check once..

1) sort the array in ascending order..

2) find the mid point

loop

3)from end of array print element and then decrease the index till mid point

4) from the starting print one element and then increase the index till midpoint-1

5) goto loop

for  example we have 1 2 3 4 5|||| 6 7 8 9 10

10 1 9 2 8 3 7 4 6 5

it will also work when elments are repeated

plz clarify...did i understood the question or not...

0
0
@Tauhin see what sir ask to get before ur comment
0
0
edited by
@ srestha  from 3 to 1 it decreasing and from 1 to 3 itz increasing and from 3 to 2 itz again decreasing...and so on....is it right...or i am on wrong track...
0
0

1 Answer

2 votes
2 votes
Best answer

A simple algorithm- iterate over the array and comparing consecutive elements as in bubble sort and swapping if the required condition is violated. 

In case elements are repeated, swap the one with the next distinct number. 

Should run in $O(n)$. 

import java.io.*;
public class Zigzag{

	int findg(Integer[] array, int el, int index){
		int i = index;
		while((i < array.length) && (array[i] == el)) 
			i++;
		if(i < array.length)
			return i;
		i = 0;
		while(array[i] == el)
			i++;
			return i;

	}
	void rearrange(Integer[] array) {
		for(int i = 0; i< array.length-1; i++)
		{
			if(array[i] == array[i+1])
			{
				int ind = findg(array, array[i],  i+2);
				if(array[ind] > array[i])
				{
					array[i%2 == 0? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 0? i+1: i];
				}
				else{
					array[i%2 == 1? i: i+1] = array[ind];  
					array[ind] = array[i%2 == 1? i+1: i];
				} 
			}
			else if(((array[i] < array[i+1]? 1: 0) ^ (i%2)) > 0)
			{
				int tmp = array[i];
				array[i] = array[i+1];
				array[i+1] = tmp;
			}
			 
		}
		
	}
	void printArray(Integer[] array){
		for(int i = 0; i < array.length; i++)
		{
			System.out.print(array[i]+" ");

		}
	}


	public static void main(String args[]) {

		Zigzag myArray = new Zigzag(); //Initialize class
		Integer[] array = new Integer[args.length];
		int i = 0;
		for(String word:args)
			array[i++]=Integer.parseInt(word);
		myArray.rearrange(array);
		myArray.printArray(array);

	}

}
selected by
by

2 Comments

Sir could u plz tell me what this code is doing? If there is repeating element this code replacing 1st element of repeating element . is it not?

if(array[ind] > array[i])

{ array[i%2 == 0? i: i+1] = array[ind];

array[ind] = array[i%2 == 0? i+1: i]; }
0
0
Not always the first element being repeated is replaced. The code is replacing the odd position if new element is larger and even position if it is smaller. There is one catch in the code which breaks the order of n complexity.
0
0