E.g. if array is // [ a, c, d, h, k, l, l, l, o, u, x, z ]
//if given m -> o
// if given k -> l
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;
}
static char search(char a[],char find)
{
if(a==null || a.length==0)
return ' ';// if nothing found
int start=0;
int end=a.length-1;
if(start>end) return ' ' ; //|| find>=a[end]) return ' ';
if(find <a[start]) return a[start];
if(start==end && a[start]>find)
return a[start];
while(start<end)
{
int mid=start+(end-start+1)/2; //to minimize over flow
if(mid+1<=end && find>=a[mid] && find <a[mid+1])
return a[mid+1];
else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])
return a[mid];
else if(find >=a[mid])
start=mid;
else if( find <a[mid])
end=mid;
else
return ' ';
System.out.println("start= " + start + ":::" + " End= " + end);
}
return ' ';//if nothing found , return special character
}
}
Time Complexity O(logn)
Space Complexity O(1)
//if given m -> o
// if given k -> l
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;
}
static char search(char a[],char find)
{
if(a==null || a.length==0)
return ' ';// if nothing found
int start=0;
int end=a.length-1;
if(start>end) return ' ' ; //|| find>=a[end]) return ' ';
if(find <a[start]) return a[start];
if(start==end && a[start]>find)
return a[start];
while(start<end)
{
int mid=start+(end-start+1)/2; //to minimize over flow
if(mid+1<=end && find>=a[mid] && find <a[mid+1])
return a[mid+1];
else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])
return a[mid];
else if(find >=a[mid])
start=mid;
else if( find <a[mid])
end=mid;
else
return ' ';
System.out.println("start= " + start + ":::" + " End= " + end);
}
return ' ';//if nothing found , return special character
}
}
Time Complexity O(logn)
Space Complexity O(1)
I liked your xoring approach. I used to think that 2nd approach is the best solution, but liked your data. Here is my blog with same post. Planning to borrow xoring approach from you.
ReplyDeleteNice post. I have done the same thing....but in java - http://k2code.blogspot.com/2014/04/given-array-arr-find-maximum-j-i-such.html
ReplyDeletevoid prime(int n)
ReplyDelete{
int i,d,c=0;
d = (int)Math.sqrt(n);
for(i=2;i<=d;i++)
{
if(n%i==0)
{c++;
break;}
if(c==1)
System.out.println("prime number");
else
System.out.println("not prime number");
}
}
In method B, pop() is wrong. It throws NoSuchElementException.
ReplyDeleteIt should be
public Object pop()
{
if(q1.isEmpty()){
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
}else {
while(q1.size()!=1)
{
q2.add(q1.remove());
}
while(!q2.isEmpty())
{
q1.add(q2.remove());
}
return q1.remove();
}
}