gerardo.ruiz@aiesec.net
BAN USERint fibonacci(int n)
{
int a=1;
int b=1;
int sol=a+b;
if((n==1)||(n==2)){return 1;}else if(n<1){return -1;}
else{
for(n>1;n--)
{
a=b;
b=sol;
sol=a+b;
}
return sol;
}
}
In place. O(n*log(n))
void intersection(int[] a, int[] b, int[] solution)
{int i=0,j=0r=0;
a.sort();
b.sort();
while((i<a.length)&&(j<b.length))
{
if(a[i]==b[j])
{
solution[r]=a[i];
r++;
i++;
j++;
}
else if(a[i]<b[j]){
i++;
}else{
j++;
}
}
}
//O(n)
int Palindromes(char[] s)
{
int count=0;
int m=s.Length/2;
if((s==null)||(s.Length==0))
{
return 0;
}
else{
if(s.Length%2==1)
{
int i = 1;
while((i+1)<s.Length)
{
if (s[i - 1] == s[i + 1])
{
count++;
}
i++;
}
}else{
int i = 2;
while ((i+1) < s.Length)
{
if ((s[i - 1] == s[i]) && (s[i + 1] == s[i - 2]))
{
count++;
}
i++;
}
}
} return count;
}
Print Palindromes(char[] ar, int left, int right)
{
if((left<right)&&(left!=-1)&&(right<ar.length))
{
if(((right-left)>2)&&(ar[right]==ar[left]))
{
Print(ar,left,right);
}
if(ar[left-1]==ar[right+1])
{
Palindromes(ar,left-1,right+1);
}
Palindromes(ar,left,left+2);
Palindromes(ar,out,left-1,left+1);
}
}
They say that in O(n) and it is only for integer. So we can the following:
int[] unsorted; //here is the input
int[] output;
int[] tmp;
int min=FindMax(unsorted);//O(n)
int max=FindMin(unsorted);//O(n)
int length=Math.Abs(max-min)
output=int[length];
tmp=int[unsorted.length];
for(int i=0;i<length;i++)//O(n)
{//Initializing
tmp[i]=0;
}
int inp;
for(int i=0;i<length;i++)//O(n)
{//Using the value as an index
inp=input[i];
tmp[inp-min]+=1;
}
int index=0;
int j=0;
for(int i=0;i<length;i++)//O(n)
{
if(tmp[i]!=0)//No occurrences
{index=0;
while(index<tmp[i])
{
output[j]=i-min;
j++;
index++;
}
}
//The final anwser is in output
//O(5n)==O(n)
}
To solve this problem, imagine that the array is triplied, I mean if we write 2, 5, -6, 3, 7 in the following way:
5, -6, 3, 7, 2, 5, -6, 3, 7, 2, 5, -6, 3. We can build an array with dimensions multiplied by 3 and It would O(3*n)=O(n).
The second and more efficient approach would be using modular numbers to transverse the array. The code could be the next:
- gerardo.ruiz@aiesec.net February 12, 2012