Please give review to this post http://rawjava.blo…
Unknown - Apr 1, 2015
Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html
Good question and equally good answer..Enjoyed your post :)
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.
[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.
[Read More]
Linear Search on Array
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.
[Read More]
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
for(int j=arrIndex/2 ; j < arrIndex;j++) …
shanky - Nov 0, 2014
for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}
This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i
Hi Shanky, you are right. That’s what I have done :)
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).
[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 > x){ return -1; } if(A == x){ return high; } else{ int low = high; int higher = (int) Math.pow(2,high); if (A>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.
[Read More]
Find the minimum element in the rotated sorted sorted array
def findMin(arr): print(“Finding min in a…
Anonymous - Sep 4, 2014
def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)
low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high
if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]
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,
[Read More]