supershal
BAN USERHere is klogn solution using Binary search.
int main(void) {
int a[] = {1,1,1,2,2,2,3,4,4,4,4};
int max = 0;
int size = sizeof(a)/sizeof(a[0]);
int maxRepetitions = numberWithRepetitions(a, 0, size, max);
printf("%d", max);
return 0;
}
int numberWithRepetitions( int[] a, int low, int high, int *maxNo){
if(a.length == 0){
return 0;
}
if( a.length == 1){
*maxNo = a[0];
return 1;
}
int mid = high + low/2;
if( a[low] == a[mid] && a[high] == a[mid]){
*max = a[low];
return high-low ;
}
int range = 0;
int leftHigh = mid;
while( a[mid] == a[leftHigh] ){
range ++;
leftHigh--;
}
int rightLow = mid+1;
while(a[mid] == a[rightLow]){
range++;
rightLow++;
}
*max = a[mid];
return (max(range,
(max(numberWithRepetitions(a, low, leftHigh, &maxNo),
numberWithRepetitions(a, rightLow, right, &maxNo));
}
{{
-> two arrays of length n
-> made up of 0 and 1
-> m-n should be max;
-> equal no of 0 and 1.
-> find m and n in O(n)
-> find equal no of 0 and 1. 0 = -1 and 1 = +1
-> min index of equal 0,1 of a and max index of equal 0,1 wiill give m, n
public class findMaxMN(int a[], int[b]){
int a_min = n+1, b_min = n+1, a_max=-1, b_max=-1;
int a_count = 0 , b_count = 0;
for(int i=0;i< n;i++){
if(a[i] == 1){
a_count++;
}else{
a_count--;
}
if(b[i] == 1){
b_count++;
}else{
b_count--;
}
if(a_count == 0){
a_min = min(a_min, i);
a_max = max(a_max, i);
}
if(b_count == 0){
b_min= min(b_min,i);
b_max= max(b_max, i);
}
}
if( a_min == n+1 || b_min ==n+1){
System.out.println("equal no of 0 and 1 not found");
}
if( a_min == n+1 && b_min != n+1){
m = b_min;
n = b_max;
}
if( b_min == n+1 && a_min != n+1){
m = a_min;
n= a_max;
}
m = min(a_min, b_min);
n = max(a_max, b_max);
}
}}
1) compare text with length n with first n characters of the main string.
2) if all characters matches then return 0
3) else increment index by 1 and recursively search main string from the next position to end of the main string until match is found.
String mainText = "who am i? Spiderman Or Superman";
String searchText = "Spiderman";
public int contains(String mainText, String searchText){
if(mainText.length() < searchText.length()){
return -1
}
if( mainText.subString(0, searchText.length()).equals(searchText)){
return 0;
}else{
return 1 + contains( mainText.subString(1, mainText.length()), searchText) ;
}
}
//correction in last part of the code
- supershal March 23, 2014