apoorvagaurav
BAN USERTraverse the array from left to right and keep on storing the number of 1s till that index at each status.
Once traversal is done, traverse it from right to left, if the current index is more than 0 then replace current element with 1 and decrease the next element by 1. If you hit a 0 then all elements left to it should be 0.
public class ZeroOneSeparator {
public static void zeroOneSeparator(int[] inputArr){
for(int i = 1; i < inputArr.length; i++){
inputArr[i] = inputArr[i-1] + inputArr[i];
}
for(int i = inputArr.length - 1; i > 0 ; i--){
if(inputArr[i] > 0){
inputArr[i-1] = inputArr[i] - 1;
inputArr[i] = 1;
}else
inputArr[i-1] = 0;
}
for(int i = 0; i < inputArr.length; i++)
System.out.print(inputArr[i]);
}
public static void main(String[] args) {
int[] inputArr1 = {1,0,1,0,1,1};
ZeroOneSeparator.zeroOneSeparator(inputArr1);
System.out.println("");
int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
ZeroOneSeparator.zeroOneSeparator(inputArr2);
int[] inputArr3 = {};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr3);
int[] inputArr4 = {0,0,0,0,0,0};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr4);
int[] inputArr5 = {0,1,0,1,0,1,0,1};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr5);
int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
System.out.println("");
ZeroOneSeparator.zeroOneSeparator(inputArr6);
}
}
Lets say BSTs are of m and n elements respectively. By doing individual in order traversal of each BST we can get two sorted linked list of m and n elements which will be achieved in O(m) and O(n). merging these to form an array is of O(m+n). Now creating a balanced BST out of this array will again be O(m+n), we can use the simple technique shown.
- apoorvagaurav July 10, 2012