kirankumarcelestial
BAN USERThis solution does not even scale for positive numbers.
Lets consider val = 1001
The result from tour code returns 7, but the actual result is 6.
int main()
{
int num=10;
int count=0;
while(num)
{
count +=num%2 ==0? 0:1;
num = num>>1;
}
cout<<count;
return 0;
}
I guess it should be right or down, we cannot solve with left or right.
- kirankumarcelestial March 28, 2014int CompareSpam(string spamstring,int i, string input, int j)
{
if(i==0 && j==0)
return 1;
if(spamstring[i] != input[j])
return 0;
else if(spamstring[i] == input[j])
{
while(spamstring[i] == input[--j])
continue;
if((i==0) && (j<=0))
return 1;
return CompareSpam(spamstring,--i,input,j);
}
return 0;
}
int detectspam(string *spamlist,int i, string input)
{
if(i < 0)
return 0;
if(CompareSpam(spamlist[i], spamlist->length()-1,input, input.length()-1))
{
cout<<"FOUND SPAM :"<<spamlist[i]<<endl;
return 1;
}
return detectspam(spamlist,--i,input);
}
int main()
{
/*
blob => bbbblllllllooooooooobbbbbbbbb
cool => ccccccooollllllllllllll
*/
string c[2] ={"blob","cool"};
string input ="cccccollll";//bbbblllllllooooooooobbbbbbbbb";
cout<<detectspam(c,sizeof(c) / sizeof(c[0]) -1, input);
return 0;
}
The Trie is a better implementation for dictionary, and the search complexity will be O(n).
But the space complexity is bit of a concern if it is in term of billion of words.
Prefix tree could be another way that could provide you with O(nlogn) complexity.
You can just use a Matrix of Bitarray to represent the parking lot, and use a Queue to update empty one. and when some new vehical arrives you can take the entry from queue and return it.
- kirankumarcelestial February 13, 2014The easiest way that i can think of quickly is:
Create a array whose length is all the combination of sequence :
Arr[Home+Search+Search]
Arr[Search+Search+Search]
Arr[Search+Search+Checkout]
and increment Arr[i] once you find a sequence.
Recursive Solution that sorts both clockwise and anticlockwise.
# include <iostream>
using namespace std;
int MinElement(int *arr, int low, int high)
{
int mid, min, min1;
if(low >= high)
return -1;
mid = (low + high)/2;
if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1])
return arr[mid];
if(arr[mid] > arr[mid-1] && arr[mid-1] < arr[mid+1])
return MinElement(arr,low,mid);
else
return MinElement(arr,mid,high);
}
int main()
{
//int arr[6] = { 3, 2, 1, 6, 5, 4 };
int arr[9] = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));
return 0;
}
Recursive Solution, which can find min Element even if the array is roated Either Clockwise or Anticlock wise.
Complexity : O(n log n)
# include <iostream>
int MIN(int a, int b)
{
return a>b?b:a;
}
int MIN(int a,int b,int c){
int min = 0;
if(a>b)
min = b;
else
min =a;
if(min >c)
return min;
else
return c;
}
using namespace std;
int MinElement(int *arr, int low, int high)
{
int mid, min, min1;
if(low >= high)
return -1;
mid = (low + high)/2;
if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1])
return arr[mid];
if(arr[mid] > arr[mid-1] && arr[mid-1] < arr[mid+1])
return MinElement(arr,low,mid);
else
return MinElement(arr,mid,high);
}
int main()
{
//int arr[6] = { 3, 2, 1, 6, 5, 4 };
int arr[9] = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));
return 0;
}
simple recursive solution
# include <iostream>
using namespace std;
int MinElement(int *arr, int low, int high)
{
int mid;
if(low > high)
return -1;
mid = (low + high)/2;
if(arr[mid] - arr[mid-1] > 0)
return arr[mid-1];
return arr[mid] < arr[mid-1] ? MinElement(arr,mid+1, high) : MinElement(arr,low,mid-1);
}
int main()
{
int arr[6] = { 3, 2, 1, 6, 5, 4 };
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));
return 0;
}
Since the array index starts from 0, initialize always arr[0] to 0 so that you dont have to bother about index incrementation.
#include <iostream>
# include <string>
using namespace std;
int ser(int* arr, int low, int high)
{
if(low > high)
return -1;
int mid = (low + high )/2;
if(arr[mid] == mid)
return mid;
return arr[mid] > mid ? ser(arr, low, mid -1) : ser(arr, mid+1, high);
}
int main()
{
int arr[11]={0,1,2,3,6,8,10,12,14,15,20};
cout<<ser(arr,1,11)<<endl;
return 0;
}
# include <iostream>
# include <string>
# define MAX(a,b) a>b?a:b
using namespace std;
int substring(string s, string sub)
{
int m[50][50]; //Some random number for quick prototype...
int slen = s.length()+1;
int sublen = sub.length()+1;
for(int i=0;i<s.length(); i++)
for(int j=0;j<s.length();j++)
m[i][j] = 0;
//For LCS problem start the matrix from 1 so that the logic m[i-1][j-1] does not go out of bounds.
for(int i=1;i<s.length(); i++)
for(int j=1;j<sub.length();j++)
{
if(s[i] == sub[i])
m[i][j] = 1 + m[i-1][j];
else
m[i][j] = MAX(m[i-1][j],m[i][j-1]);
}
/*
for(int i=0;i<s.length(); i++)
{
cout<<endl;
for(int j=0;j<sub.length();j++)
cout<<m[i][j]<<" ";
}
*/
return m[s.length()-1][sub.length()-1];
}
string LCS(string s, int n)
{
int max = 0;
int result=0;
string ressubstring ;
for(int i=0;i<s.length()-1; i++)
{
string sub =s.substr(i,n);
if((sub.length() == n) && (s.length() >= n))
result = substring(s,sub);
if(result > max )
{
max = result;
ressubstring = sub;
}
}
return ressubstring;
}
int main()
{
string s = "ABCACBABC";
cout<<endl<<"LCS :"<<LCS(s,3)<<endl;
return 0;
}
Use Huffman Encoding to encode the String.
- kirankumarcelestial April 01, 2014