Find Nth largest element in the rotated sorted array

Question : Find Nth largest element in the rotated sorted array
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don't know. But seeing the above array we cans see that k = 2, which is also the index of minimum element i.e. 2 here. So, 3rd largest element is counting 3rd from 2 i.e. 6. Similarly for Nth largest element, it is k+N-1. But as we can see as the array is rotated, k+N-1 may overflow array, so we need to modulo operator on k+N-1, i.e. Nth largest element lies at = (k+N-1)%arraySize.

So, the problem breaks down in 2 step

1. Find k, i.e. number of rotations. To do so please refer the post - Find the rotation count in rotated sorted array
2. Return the arr[(k+N-1)%arr.size]

Here is the pseudocode:

int findNthHigehest(int[] arr, int size, int n)
{
    int k = findRotationCount(arr, size);
    return arr[(n+k-1)%size];
}

Thanks.

Read More

Find the rotation count in rotated sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array.
So, we need to find the point of inflection where we find a point such that a[i]>a[i+1].

So, finding the minimum element in the rotated sorted array has been implemented here - Find the minimum element in rotated sorted array. Thanks.

Read More

Linear Search on Array

References
http://www.durofy.com/computing/linear-search-in-c/

Read More

Finding an integer that repeats odd number of times in an array of positive integers

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?

Solutions
Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. Thus, if a number appears a even number of times, it yield a result of 0.

For example, given the array {2, 3, 2, 3}, we have 2 and 3 repeat two times (even). Thus, if we XOR all of them together we should get 0 as the result. However, if there is an odd repeated number, the result will be the value of that number!

Code in java

public static int getIntOddlyOccured(int[] inputArr)
  {
    int oddNum = inputArr[0];
   
    for(int i = 1; i < inputArr.length; i++)
      oddNum = oddNum ^ inputArr[i];
   
    return oddNum;
  }

c implementation

int getOddOccurringNumber(int arr[], int arr_size)
{
     int i;
     int result= 0; 
     for (i=0; i < arr_size; i++)     
        result= result^ arr[i];
      
     return result;
}

Explanation: our method takes an integer array as argument. It assumes that there is one and only one odd occurring number (conditions given by the question), so it will return that number and does no validation to see whether the input in fact has only one odd repeated number. In the body, the method loops through the array and XOR all the elements together. The result will be the oddly repeated number.

The caret '^' sign means XOR (exclusive OR). And, our algorithm works because XOR of two same number is 0. For example, 2 XOR 2 = 0 because 0010 XOR 0010 = 0000. Thus, all the even repeating numbers will yield the result = 0 while the odd repeating number will yield itself as the result. In our example, we know 3 is the odd-repeating number because 3 XOR 0 = 3.

Example: let's do an example with this array {1, 4, 3, 4, 1}. The method first initializes the result oddNum to 1 and then does the for loop:

1. First iteration: oddNum = 1(0001) ^ 4(0100) = 5(0101) and i = 1
2. Second iteration: oddNum = 5(0101) ^ 3(0011) = 6(0110) and i = 2
3. Third iteration: oddNum = 6(0110) ^ 4(0100) = 2(0010) and i = 3
4. Fourth iteration: oddNum = 2(0010) ^ 1(0001) = 3(0011) and i = 4
5. Loop ends because i = 5, so we return oddNum = 3 which is the oddly repeated number in the array

This algorithm takes O(n) time complexity because it loops through the array only once. The space complexity is O(1) because we only need an additional integer for storage. Very efficient! That's all we have for now.

Approach 2 - Using the hash table
For example, we can use a hash table to maintain counts of repetition for each number in the array. Then, we look for the number with odd count.But what if someone asks "not to use any datastructure" / additional storage.

Thanks. Please let me know if you have better solution

Read More

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach.

Approach 2 :  Club binary search approach and array's random access property

Since the array is infinitely increasing i.e. we don't know array size in advance, so we can't directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). We can apply reverse of BinarySearch approach.

We can think of sorted infinite 0 and 1 array as infinite size bit stream on disk with 0 set bits followed by 1 bits.

Approach:
Start with first bit, if it is 1 we are lucky and got the switch index, else if it is 0 check the 2,4,8,16,32,64.... 2^n bits till we get first 1 set bit index say its 'i'. (We are moving by power of 2, rather than 3, 4 etc, because it minimizes the range of data to find the element). Now we have to find between index i/2 to i where the swich happened and this can be done by simple binary search (size of the array to look into is i/2).


Pseudocode:

int GetSwitchIndex()
{
  for(int i=0;;i++)//infinite loop based on break statement
  {
    int arrIndex = power(2,i);
    //lucky case - when first element is lucky
    if(array[arrIndex]==1&&i==0)
      return 0;
    if(array[arrIndex]==1)
      for(int j=arrIndex/2 ; j < arrIndex;j++)
      {
        if(array[j]==1)
          return j;//this is our index
      }
  }//end outer for loop
}

Time Complexity: log(N), N is index at which switch happened.

Read More

Searching the element in sorted infinite array of integers

Question : Given an infinite array of integers which is sorted. How would you search for an integer in this array? Here is the algo (in java):

public static int searchInf(int A[],int high,int x){
// Assume we are searching for x
  if (A[1] > x){
   return -1;
  }
  if(A[high] == x){
   return high;
  }
  else{
   int low = high;
   int higher = (int) Math.pow(2,high);
   if (A[high]>x){
    binarySearch(A,low,higher);
   }
   else{
    searchInf(A,higher,x);
   }
  }// end else
  return -1;
 }// end searchInf method 

So if we find some element greater than element x, perform normal binary search, else call the search inf function.

Complexity

Using the method of double your index until you pass it, then binary search the region you just jumped over (what it looks like your pseudocode is trying to do), the time spent should be O(log₂ n) where n is the index of the item you are searching for.
It will take you (log₂ n) tries to find the correct region, and then ((log₂ n) - 1) tries to find x within that region (since you already searched from 0..n/2, you only need to search n/2..n). Therefore, O(log₂ n + log₂ n - 1) = O(log₂ n).
However, if the "infinite array" does not contain x or any value greater than x, you will never know, because you will search forever.

Read More

Find the minimum element in the rotated sorted sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

// always restrict the search to the unsorted 
// sub-array. The min is always there.
public static int findMin(int[] a, int start, int end){
  int mid = (start + end)/2;
  if(start == mid){//only 1 element
    return a[mid+1];
  }else if(a[start] > a[mid]){
    return findMin(a, start, mid);
  }else if(a[mid+1] > a[start]){
    return findMin(a, mid+1, end);
  }
  //else{
  //  return a[mid+1];
  //}
}

To begin with we call findMin(array, 0, array.length-1).
Doing it iteratively:

// index of first element
l = 0

// index of last element.
h = arr.length - 1

// always restrict the search to the unsorted 
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
        // find mid.
        mid = (l + h)/2
        // decide which sub-array to continue with.
        if (arr[mid] > arr[h]) {
                l = mid + 1
        } else {
                h = mid
        }
}
// answer
return arr[l]

Read More

Search an element in the sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer: We can do a binary search with some modified checks.

So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.

Pseudocode: 

1. Find the middle of array
2. Select the sorted array part
   If a [middle]  >  a[start] - That means this part of array is sorted and is without rotation. So, we choose array to search as [start] to a[middle] otherwise we choose a[middle] to a[end].
3. Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key x lies in range of the array, we will search for the element in that range, otherwise other range. 

So, second step helps us get the sorted array on which we can apply binary search. 

Program in java

public int rotatedSearch(int[] arr, int start, int end,
                          int x){
    if(arr[start] == x){
        return start;
    } else if(arr[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }

    int middle = (start + end) / 2;

//we have no rotation between start and middle, i.e. normal sorted array
//if left sub array is sorted
   if(arr[start] <= arr[middle]){
//if x is less than middle - then x may lie in this part of array
        if(x <= arr[middle] && x >= arr[start]){
            return rotatedSearch(arr, start, middle-1, x);
        } else {
            return rotatedSearch(arr, middle+1, end, x);
        }
    }
//if right sub array is sorted
    else if(arr[middle] <= arr[end]){
        if(x >= arr[middle] && x <= arr[end] ){
            return rotatedSearch(arr, middle+1, end, x);
        } else {
            return rotatedSearch(arr, start, middle-1, x);
        }
    } else {
        return -1;
    }
}

Time Complexity - O(log n)
Thanks.

Read More

Binary search on Array - Recursive and iterative

There are two basic searching algorithms used. One is the simplest technique and is discussed here.
Here we will discuss the binary search method.

The other search method is the binary search method. The binary search technique is a very fast and a more efficient technique when compared to the linear search method, and gets us the result in O(log n) where n is number of elements. The only requirement for this method is that the input array of elements must be in the sorted order.

In binary search, the target value (the element that has to be searched) is searched with the center element in the array. If the target value and the center element is equal, searching is complete, if it is not equal then the sample space is split into two parts, the element group on the left of the center element (values lower than the center element) or the element group on the right of the center element (values larger than the center element). As the elements are in the sorted order, the search process will now be restricted to either of the two element groups. As the process is repeated, the target value is found eventually.

The binary search process is explained below with the help of figures. Consider the sample space of 10 elements 1, 5, 7 ,10, 15, 17, 19, 23, 30 and 34 where the element 30 is the target value that has to be found.

In the beginning of the search process, 1 is the low value and 34 is the high value, the middle value is found using the formula (low+high)/2 and thus 15 is the center element or the middle element.

Now as the target value 30 is greater than the center value 15, the search process in the next iteration will be restricted to the right half of the sample space i.e. from 17 to 34. For the second iteration, 17 and 34 are the low and high values respectively and 23 is the center value.

The target value is compared with the present center value i.e. 23. So the search process will be restricted to the elements on the right to the center element 23. So the low value is 30 and the high value is 34. Now, the center element is 30. In the third iteration, the target value equals the center element 30 and thus the searching process is complete.

 Iterative Implementation

int binarySearch(int arr[],int size, int item)
{
   int left, right, middle;
   left  = 0;
   right = size-1;

   while(left<=right)
   {
      middle = ((left + right)/2);

      if(item == arr[middle])
      {
        return(middle);
      }

      if(item > arr[middle])
      {
        left  = middle+1;
      }
      else
      {
        right = middle-1;
      }
   }

   return(-1);
}

Recursive Implementation:

public static int rBinarySearch(int[] sorted, int first, 

int upto, int key) {
    
    if (first < upto) {
        int mid = first + (upto - first) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            return rBinarySearch(sorted, first, mid, key);
            
        } else if (key > sorted[mid]) {
            return rBinarySearch(sorted, mid+1, upto , key);
            
        } else {
            return mid;   // Found it.
        }
    }
    return -(first + 1);  // Failed to find key
}

Read More