mahesh_ostwal@yahoo.in
BAN USERMy turn to take a stab at it
/* To find the number of rotations in an array in less than O(n) time */
#include <stdio.h>
void findRotations(int arr[], int size);
int main(void)
{
int arr1[]={7,8,9,10,1,2,3,4,5,6};
int size1=sizeof(arr1)/sizeof(arr1[0]); //Size of arr1[]
int arr2[]={4,5,6,7,8,9,10,1,1,1,2,3};
int size2=sizeof(arr2)/sizeof(arr2[0]); //Size of arr2[]
findRotations(arr1, size1); //Calling function, passing arr1[]
findRotations(arr2, size2); //Calling function, passing arr2[]
return 0;
}
//Function that employs binary search to find the number of rotations
void findRotations(int arr[], int size)
{
if(size==0 || size==1 || size==2)
return;
int l=0, r=size-1, mid=l+(r-l)/2;
//Logic is to zero-in on the smallest element in the array using binary search
while(l<=r)
{
if(arr[mid-1]>arr[mid] && arr[mid]<=arr[mid+1]) //Minimum found condition
{
printf("\nNo. of rotations are %d or %d\n", mid, size-mid);
return;
}
else if(arr[mid]-arr[l]<0) //Passing this condition binary search would
r=mid-1; //continue on the left sub-array
else
l=mid+1;
mid=l+(r-l)/2;
}
return;
}
?! Creation of the hash map is O(n), as bad as linear search.
- mahesh_ostwal@yahoo.in May 09, 2013Working C Code with edge cases considered
Time Complexity : O(n)
Each time I start with the intention of writing some clean and elegant code but inevitably end with a not so pleasing piece
/* Program to find the length longest substring which has
two and only two unique characters */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longest2CharSS(char *str, int len);
int findPos(char *str, int i);
int main(void)
{
char str[]={"aabbabbbadef"};
int len=strlen(str);
//Calling longest2CharSS() within the
//print statement itself
printf("\nThe length of the longest such substring : %d\n",
longest2CharSS(str, len));
return 0;
}
//Function that returns the length of the longest such substring
int longest2CharSS( char *str, int len)
{
if(len==0 || len==1) //Edge case where two unique
{ //characters are out of the question
printf("Error!\n");
exit(0);
}
char twoch[2]; //Two characters array to store the two unique
//characters of the current valid substring
int start, end, len_lss, i=1, l_start, l_end, j=0;
twoch[0]=str[0];
char cpstr[len];
while(str[i]==twoch[0]) //To get to the next distinct character
i++;
if(i>=len)
{
printf("Error!\n");
exit(0);
}
twoch[1]=str[i];
start=0;l_start=0;
end=i;l_end=0;
while(i<len)
{
if(str[i]!=twoch[0] && str[i]!=twoch[1])// If a new character is seen
{
start=findPos(str, i-1);//Start is assigned the position of the least
//recent continuous str[i-1] character
end=i;
if((end-start)>len_lss)//If current valid substring has a length
{ len_lss=end-start; //greater than the length of the longest
//valid substring seen until now
l_start=start;
l_end=end;
}
}
else if((str[i]==twoch[0])^(str[i]==twoch[1])) //If the present character
{ //is same as any one of the
end++; //present valid substring character
if((end-start)>len_lss)
{ len_lss=end-start;
l_start=start;
l_end=end;
}
}
i++;
}
for(i=l_start; i<=l_end-1;i++)//Copy the longest substring into cpstr
{
cpstr[j]=str[i];
j++;
}
printf("The longest such substring : %s", cpstr);
return len_lss;//Returning length of the longest substring
}
//Function to find the position of the oldest occurrence of the
//character condition being that it is a continuous occurrence
int findPos(char *str, int i)
{
int j=i;
while(str[j]==str[i])
j--;
return (j+1);
}
Working C Code, messy though
/* Program to print instances of elements which have duplicates in a given
array */
#include <stdio.h>
#include <stdlib.h>
int* findDupEle(int arr[], int size);
int main(void)
{
int arr[]={2,1,2,4,3,1,5,1};
int size=sizeof(arr)/sizeof(arr[0]);
int *dup=findDupEle(arr, size);//Pointer to the array containing
//duplicates is returned
int i=1;
int k=*dup;
//Printing the elements which have repeats
printf("\nThe Array of Duplicates contains : ");
while(i<=k)
{
printf("%d\t",*(dup+i));
i++;
}
printf("\n");
return 0;
}
//Function that returns the array containing instances of
//elements with duplicates
int* findDupEle(int arr[], int size)
{
if(size==0 || size==1)
{
printf("\nErroneous Input!\n");
abort();
}
int hasha[101]={0};//Sort of hash which accepts values from 1 to 100
int count=0;
int* dup=(int*)malloc(sizeof(int)*size+1);//Dynamically declare and allocate
//memory to the array which is
//going to store duplicates
int i=0,k=0;
while(i<size)
{
if(hasha[arr[i]]==0)//If the value is being seen for
hasha[arr[i]]=1;//the first time this is executed
else if(hasha[arr[i]]==1)
{
dup=dup+1;//dup pointer is incremented
*dup=arr[i];
k++;
hasha[arr[i]]++;//hash is also incremented and hence
//elements which are seen for the 2nd
//time only are put into the dup array
}
i++;
}
dup=dup-k;
*dup=k;
return dup;
}
Can you please explain the underlying logic?
- mahesh_ostwal@yahoo.in April 07, 2013
Great solution! Elegant!
- mahesh_ostwal@yahoo.in August 18, 2013