Find an Item in a Sorted Array with Shifted Elements
Problem: You are given a sorted array with shifted elements. Elements can be shifted to the left or right by ‘i’ number of places. The sign of ‘i’ denotes the direction of the shift. For positive ‘i’ direction of shift is right and left for negative ‘i’.
For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,
For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.
Write code to find if a given number is present in this array.
Solution: The brute force method to search all elements in the array would yield an O(n) solution, so obviously that’s not the best approach. We are not leveraging the sorted nature of the array in this case.
Now, how can we leverage the sorted nature of the array? Let assume that ‘i’ was 0. In that case the array would be sorted and not shifted at all (0 shift). Whats the fastest way to search in a sorted array? Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n), which is obviously better than n.
But, the fact that the array is shifted by ‘i’ number of elements complicates things a little bit. Now, instead of splitting the array in equal halves, we split the array at the shift index and do a recursive binary search. There are issues we need to tackle when the shift is greater than the length of the array or if the shift is negative. I guess the code below will make much more sense than my description of the solution.
Code: We will assume that we are provided with a method below that does binary search for us and won’t bother implementing it here.
// myArray is the input array
// startIndex and endIndex are the indexes in the
// array where the binary search starts and ends
// The method returns the index of the searchVal
// if found in the array, else it returns -1
int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal);
// this method will return the index of the searchVal
// if found, else it return -1
int SearchElement(int[] myArray, int shift, int searchVal)
{
// to take care of scenarios where the shift is more
// than the length of the array
shift = shift % myArray.Length;
// -ve shift can be seen as positive shift equal to
// the length of the array - ( -ve shift)
if (shift < 0)
shift = myArray.Length + shift;
if(myArray[shift] <= searchVal &&
myArray[myArray.Length - 1] >= searchVal)
{
return BinarySearch(myArray, shift, myArray.Length - 1, searchVal);
}
else if(myArray[0] <= searchVal &&
myArray[shift - 1] >= searchVal)
{
return BinarySearch(myArray, 0, shift-1, searchVal);
}
return -1;
}
Array: Find the number with odd number of occurrences
Problem: You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.
Solution: A naive approach would be to loop over the elements of the given array and keep a count of each integer in a hash table or another counter array. But, this quickly becomes unfeasible as the range of integers could be 2^31 (one less). This is an O(n) solution that takes at memory O(range(n)).
The next approach is to sort the array and then loop on it counting occurrences of the integers. When there is a change in the integer we check its count to see if its odd or even. If its odd we have found our special integer. This is an O(n log n) solution that uses constant memory.
Lets try to see if we can use the property that there is one number that occurs odd number of times and every other number occurs even number of times. Since an even number is divisible by 2, you could think of the even occurrences as being present in pairs. The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we’d be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.
XOR will do the trick. Its gives you O(n) solution with no extra memory.
Ex: 3,5,3,2,2
011 — 3
^101 — 5
———-
110
^011 — 3
———-
101
^010 — 2
———-
111
^010 — 2
———-
101 — 5 (special one)
int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];
for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}
Create Tree from Postorder, Preorder and Level Order Traversals
#include <iostream>
#include <queue>
using namespace std;
class Tree
{
class TreeNode
{
public:
int value;
TreeNode* left;
TreeNode* right;
} ;
public:
static void preorderTraversal(TreeNode* current)
{
cout<<current->value<<" ";
if(current->left)
{
preorderTraversal(current->left);
}
if(current->right)
{
preorderTraversal(current->right);
}
}
static void inorderTraversal(TreeNode* current)
{
if(current->left)
{
inorderTraversal(current->left);
}
cout<<current->value<<" ";
if(current->right)
{
inorderTraversal(current->right);
}
}
static void postorderTraversal(TreeNode* current)
{
if(current->left)
{
postorderTraversal(current->left);
}
if(current->right)
{
postorderTraversal(current->right);
}
cout<<current->value<<" ";
}
static void levelorderTraversal(TreeNode* current)
{
queue<TreeNode*> q;
q.push(current);
TreeNode* temp;
while(!q.empty())
{
temp = q.front();
q.pop();
cout<<temp->value<<" ";
if(temp->left)
{
q.push(temp->left);
}
if(temp->right)
{
q.push(temp->right);
}
}
}
static int search(int x[],int start, int end,char value)
{
for(int i=start; i<end; i++)
{
if(x[i]==value)
{
return i;
}
}
}
static TreeNode* createTreeFromPreOrder(int inorder[],int preorder[], int start, int end)
{
static int position = 0;
if(start>end)
{
return NULL;
}
TreeNode* temp = new TreeNode();
temp->value = preorder[position++];
if(start==end)
{
return temp;
}
int mid = search(inorder,start,end,temp->value);
temp->left = createTreeFromPreOrder(inorder,preorder,start, mid-1);
temp->right = createTreeFromPreOrder(inorder,preorder,mid+1,end);
return temp;
}
static TreeNode* createTreeFromPostOrder(int inorder[],int postorder[], int start, int end)
{
static int position = end;
if(start>end)
{
return NULL;
}
TreeNode* temp = new TreeNode();
temp->value = postorder[position--];
if(start==end)
{
return temp;
}
int mid = search(inorder,start,end,temp->value);
temp->right = createTreeFromPostOrder(inorder,postorder,mid+1,end);
temp->left = createTreeFromPostOrder(inorder,postorder,start, mid-1);
return temp;
}
static TreeNode* createTreeFromLevelOrder(int inorder[],int levelorder[], int start, int end,int level)
{
if(start>end)
{
return NULL;
}
TreeNode* temp = new TreeNode();
temp->value = levelorder[level-1];
if(start==end)
{
return temp;
}
int mid = search(inorder,start,end,temp->value);
temp->left = createTreeFromLevelOrder(inorder,levelorder,start, mid-1,2*level);
temp->right = createTreeFromLevelOrder(inorder,levelorder,mid+1,end,2*level+1);
return temp;
}
};
int main()
{
int inorder[] = {5,2,7,1,8,3,9};
int preorder[] = {1,2,5,7,3,8,9};
int postorder[] = {5,7,2,8,9,3,1};
int levelorder[] = {1,2,3,5,7,8,9};
int len = sizeof(inorder)/sizeof(inorder[0]);
Tree::preorderTraversal(Tree::createTreeFromPreOrder(inorder,preorder,0,len-1));
cout<<endl;
Tree::postorderTraversal(Tree::createTreeFromPostOrder(inorder,postorder,0,len-1));
cout<<endl;
Tree::levelorderTraversal(Tree::createTreeFromLevelOrder(inorder,levelorder,0,len-1,1));
return 0;
}
Project Euler Statistics
Ronzii's Blog 