Find two Repeated or Non-Repeated numbers in the given array

Problem 1: 
There are n+2 elements, which are in the range of 1 to n. All are unique, except two numbers. Find the two repeated numbers.

eg: {4, 2, 4, 5, 2, 3, 1}
output: 2, 4

Algorithm:
Given array: int[] ar

Find XOR of all elements in input array and all numbers from 1 to n:
XOR = ar[0] ^ ar[1] ^ ... ar[n+1] ^ ar[n+2] ^ 0 ^ 1 ... ^ n

Now Get the right most set bit in this XOR Result
right_most_set_bit = XOR & (~(XOR-1))

One of the missing number will be "XOR of all array elements and all numbers from 1 to n, which are having the righ_most_set_bit set in them"
Other missing number will be "XOR of all array elements and all numbers from 1 to n, which are not having the righ_most_set_bit set in them"

Program:

public class FindRepeatedNos {
static public void main(String[] args) {
int[] ar = {4, 2, 4, 5, 2, 3, 1};
int n = 5;

int x = 0, y = 0;

int xor = 0;

for(int i=0; i<ar.length; i++)
xor = xor ^ ar[i];

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

//Get the right most digit
int right_most_bit = xor & (~(xor-1));

for(int i=0; i<ar.length; i++) {
if((ar[i] & right_most_bit) == 0)
x = x ^ ar[i];
else
y = y ^ ar[i];
}

for(int i=1; i<=n; i++) {
if((i & right_most_bit) == 0)
x = x ^ i;
else
y = y ^ i;
}

System.out.println(x);
System.out.println(y);
}
}

Problem 2:

Given an array containing n elements. All the elements are repeated twice, except two numbers, which occurred only once. Find those two numbers. No range specified for input elements.

eg: {2, 4, 7, 9, 2, 4}
output: 7, 9

Algorithm:

It is similar to above algorithm, except that we dont have 1 to n numbers here. So only one for loop for all xor operations.

Program:

public class FindNonRepeatedNos {
         static public void main(String[] args) {
int[] ar = {2, 4, 7, 9, 2, 4};

int x = 0, y = 0, xor = 0;

for(int i=0; i<ar.length; i++)
xor = xor ^ ar[i];

int right_most_set = xor & (~(xor-1));

for(int i=0; i<ar.length; i++) {
if((ar[i] & right_most_set) == 0)
x = x ^ ar[i];
else
y = y ^ ar[i];
}

System.out.println(x);
System.out.println(y);
}
}

Print Left View of a Binary Tree

Left view of a Tree is: When you view the Tree from left side of the Tree, where you will be able to see only the first element in each level.

So other way of asking the question is: Print the first node in each Level of the Tree.

eg:

                              1

               2                               3

                     4                   5           6

               7                               8

                                         9

                                              10

Output: 1 2 4 7 9 10

Algorithm:

Logic is to keep a global variable called "level", with initial value as 0

Traverse the tree in PreOrder(DLR)

Now for each node, check whether its height is equal to count or not.

If equal, it means that this is the left most element in that level that we encountered. So print it and increase the count, so that other elements in the same height wont be printed.

Do this recursively.

Code:

class TreeLeftView {
        static int level = 0;

        static public void print(TreeNode root, int height) {
                if(root == null)
                        return;

                if(level == height) {
                        System.out.print(root.getData() + " ");

                        ++level;
                }

                print(root.getLeft(), height + 1);
                print(root.getRight(), height + 1);
        }

        static public void main(String[] args) {
                TreeNode root = TreeUtil.getBinaryTree2();

                print(root, 0);

                System.out.println();
        }
}

Diameter of a tree: Longest path between any two nodes

Diameter of a tree can be from any one of the following:
1. Longest path of the tree passes through the root
2. Longest path is completely in left sub tree
3. Longest path is completely in right sub tree

To find the Longest path passing through the root, is nothing but the height of the node, ie. "height(left) + height(right) + 1"

Other two can be find in recursive way.

Algorithm:
Each time we are trying to find out height of left/right sub trees. We can use an independent function to calculate height of tree, but that takes O(n) each time. Instead we can make the function to return height also along with diameter.

result[] = {diameter, height}

diameter passing through root is: rootDia=leftResult[1] + rightResult[1] + 1

leftDia = leftResult[0];
rightDia = rightResult[0];

result[1] = max(leftResult[1]+1, rightResult[1]);

return max(rootDia, max(leftDia, rightDia));

Code:

class DiameterOfTree {
        static public int[] getDia(TreeNode root) {
                int[] result = {0, 0};

                if(root == null)
                        return result;

                int[] leftRes = getDia(root.getLeft());
                int[] rightRes = getDia(root.getRight());

                int leftHt = leftRes[1];
                int rightHt = rightRes[1];

                int leftDia = leftRes[0];
                int rightDia = rightRes[0];

                result[0] = Math.max(leftHt+rightHt+1, Math.max(leftDia, rightDia));
                result[1] = Math.max(leftHt+1, rightHt+1);

                return result;
        }

        static public void main(String[] args) {
                System.out.println(getDia(TreeUtil.getBinaryTree())[0]);
                System.out.println(getDia(TreeUtil.getBinaryTree1())[0]);
        }
}

Modified Binary Search: Search for an element in Sorted and Rotated array

Problem:

Lets say there is a sorted array, but it is rotated by some positions.
Now we need to search for an element with O(log n) time complexity.

Solution:
If the array is completely sorted, then we can apply binary search on it.
But here it is not the case, but still we can use the rotation information and apply modified binary search.

Divide the array into two parts wrt middle element.
Now at this point, one of the left/right sub arrays, one sub array should be sorted and other is not.
We can use this information to solve the problem.

Algorithm:
Find the Middle element

If the data is equal to middle then return
else if (ar[left] < ar[mid]) { //means left array is sorted
    if(data >= ar[left] and data < ar[mid])
        high = mid - 1;
    else //search in the right sub array
        low = mid + 1;
} else { //right array is sorted
    if(data > ar[mid] && data <= ar[high])
       low = mid + 1;
    else
       high = mid - 1;
}

Code:

import java.util.Arrays;

class RotatedSortedAr {
        static public int rotatedBinSearch(int[] ar, int data) {
                int low = 0, high = ar.length - 1;
                int mid = -1;

                while(low <= high) {
                        mid = low + ((high-low)/2);

                        if(ar[mid] == data)
                                return mid;

                        if(ar[low] < ar[mid-1]) {
                                //left array is sorted

                                if(data >= ar[low] && data < ar[mid])
                                        high = mid - 1;
                                else
                                        low = mid + 1;
                        } else {
                                //right array is sorted
                                if(data > ar[mid] && data <= ar[high])
                                        low = mid + 1;
                                else
                                        high = mid - 1;
                        }
                }

                return mid;
        }

        static public void main(String[] args) {
                int[] ar = {4, 5, 6, 7, 8, 9, 1, 2, 3};

                int key = 3;

                int pos = rotatedBinSearch(ar, key);

                System.out.println(Arrays.toString(ar));
                System.out.println("Position of " + key + " is: " + pos);
        }
}

Time Complexity:
O (log n)

Maximum Number in Sliding Window

Maximum in Sliding Window Algorithm:

Given an input array and a window size, we need to output the maximum element each time in the window, sliding the window by one element every time.

For eg:
input:   {1, 3, -1, -3, 5, 3, 6, 7};
output: {3, 3, 5, 5, 6, 7}

Points to remember:

1. We always maintain the largest element index at the start of the deQueue.
2. When we are inserting a new element index into the Deque, do the following:
- Compare the inserting element with the queue elements from its end. If anything is lower than the inserting element, then remove it.
- Now check the validity of indices from starting of the queue. If any element is out of current window range, then remove it from queue.

Algorithm:

1. Take the input array and window size
2. initialize output array with a size of (input.length-window size)
3. Create a Double Ended Queue - Dequeue (size will be maximum of window size)

4. Now as an initial step, fill the Dequeue as below.
for(int i=0; i<window.size; i++) {
Do the following recursively, if the queue is not empty.
If the element to be inserted is greater than the last element of the DeQueue, then delete the last element of the Dequeue

Now insert the index of the element to be inserted, i.e "i" at the end of the queue.
}

5. Now follow the below steps for remaining elements:
for(int i=window.size; i<input.size; i++) {
a) Get the first element(i.e. index) of the queue and insert it to output array at (i-w) position
b) Compare the inserting element with the queue elements from the end. If any queue is element less than inserting element, then delete it.
c) Check the index validity of queue elements from its start. If any element is out of the window range, then delete it.
d) insert the current element to the queue.
}

6. Get the first element from the queue and insert it to the output array.


Java Code:

import java.util.Arrays;

class MaxSlidingWindow {
        static public int[] maxSlidingWindow(int[] ar, int w) {
                int n = ar.length;
                int[] out = new int[n-w+1];

                DeQueue queue = new DeQueue();

                //prepare initial window
                for(int i=0; i<w; i++) {
                        while( !queue.isEmpty() && ar[i] > ar[queue.getLast()])
                                queue.deleteLast();

                        queue.insertLast(i);
                }

                for(int i=w; i<ar.length; i++) {
                        out[i-w] = ar[queue.getFirst()];

                        //clear the queue wrt the element to be inserted
                        while(!queue.isEmpty() && ar[i] > ar[queue.getLast()])
                                queue.deleteLast();

                        //clear the queue wrt the out of indices
                        while(!queue.isEmpty() && queue.getFirst() <= (i-w))
                                queue.deleteFirst();

                        queue.insertLast(i);
                }

                out[n-w] = ar[queue.getFirst()];

                return out;
        }

        static public void main(String[] args) {
                int[] ar = {1, 3, -1, -3, 5, 3, 6, 7};
                int[] out = maxSlidingWindow(ar, 3);

                System.out.println(Arrays.toString(ar));
                System.out.println(Arrays.toString(out));
        }
}


eg:
i/p: {1, 3, -1, -3, 5, 3, 3, 6, 7}
w=3
Queue is empty

Filling the window initially:
1. i=0
Since queue is empty, just insert this index into Queue.
Queue: {0}

2. i=1
ar[i] > ar[queue.getLast()] ==> ar[1] > ar[0] ==> 3 > 1 ==> correct
remove the ar[queue.getLast()] from Queue. Now the Queue is empty.

insert current element index to queue.
Queue: {1}

3. i=2
since ar[i] > ar[queue.getLast()] ==> ar[2] > ar[1] ==> -1 > 3 ==> is wrong
So dont do anything

insert current element index to queue.
Queue: {1, 2}


Starting the actual process:
1. i=3
insert the queue.getFirst() to output array:
==> output={3, 0, 0, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[3] > ar[2] ==> -3 > -1 ==> is wrong

valid window range: [i-w+1 to i] ==> [1, 3]
all queue indices are valid

insert current element index to queue.
Queue: {1, 2, 3}

2. i=4
insert the queue.getFirst() to output array:
==> output={3, 3, 0, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[4] > ar[3] ==> 5 > -3 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {1, 2}

again: ar[i] > ar[queue.getLast()] ==> ar[4] > ar[2] ==> 5 > -1 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {1}

again: ar[i] > ar[queue.getLast()] ==> ar[4] > ar[1] ==> 5 > 3 ==> correct
remove the ar[queue.getLast()] from Queue:
Queue ==> {}

Check the validity of queue indices from starting: valid window range: [2, 4]
Since queue is empty. dont do anything.

insert current element index to queue.
Queue: {4}

3. i=5
insert the queue.getFirst() to output array:
==> output = {3, 3, 5, 0, 0, 0}

ar[i] > ar[queue.getLast()] ==> ar[5] > ar[4] ==> 3 > 5 ==> is wrong.
dont do anything

valid window range: [3, 5]
queue indices are valid.

insert the current index to queue:
Queue: {4, 5}

...