Daru
BAN USERclean code using recursion. Divide the output by the all combination to have the probability.
working for all the example cases mentioned in this thread.
static int findProbability (int n, int x, int m) {
if (x <= 0) return pow(m,n);
if (n == 0) return 0;
int result = 0;
int i;
for (i = 1; i <= m; i++) {
result += findProbability(n-1, x-i, m);
}
return result;
}
We need to examine all possible pairs in order to handle all possible cases.
static int median(int a, int b, int c) {
int m = (a<=b)?a:b; // min(a,b)
int n = (a<=c)?a:c; // min(a,c)
m = (m>=n)?m:n; // max(m,n)
n = (b<=c)?b:c; // min(b,c)
return (m>=n)?m:n; // max(m,n)
}
To my understanding, the sign of element at each position is used to indicate the repeating pattern. So negative means a number appears for odd number of times, and positive means appearing for even number of times. But what if a number never shows up? in that case, the sign is positive, how to catch this case?
- Daru August 01, 2012This sln seems to read all the data out of the file, and return the total number of bytes. However, I am not sure whether the question is asking for reading a specified number of bytes ( reads any number of chars from the file).
Anyway, the suggested API doesn't contain any argument taking in the desired number of bytes to read.
O(n)
static void commonNum(int* arr1, int* arr2, int n, int m)
{
int i, j;
i = 0;
j = 0;
while (i < n && j < m)
{
if (arr1[i] == arr2[j])
{
cout << arr1[i] << ' ';
for (++i; i < n; i++)
{
if (arr2[j] < arr1[i])
{
break;
}
}
}
else if (arr1[i] < arr2[j])
{
for (++i; i < n; i++)
{
if (arr2[j] <= arr1[i])
{
break;
}
}
}
else if (arr1[i] > arr2[j])
{
for (++j; j < m; j++)
{
if (arr2[j] >= arr1[i])
{
break;
}
}
}
}
cout << endl;
}
This is a tested code in C++:
static int seqRun (int N, int M, int K, int L)
{
int result = 0;
for (int i = 1; i <= K; i++)
{
vector<int> seq;
seq.push_back(i);
result += seqRun(N,M,K,L,0,-1,seq);
}
return result;
}
static int seqRun (int N, int M, int K, int L, int run, int direct, vector<int> seq)
{
int seq_len = seq.size();
if (run > M)
return 0;
if (seq_len == N)
{
if (run < M)
return 0;
for (int i = 0; i < N; i++)
cout << seq[i] << ' ';
cout << endl;
return 1;
}
int result = 0;
int last_val = seq.back();
for (int i = last_val-L; i < last_val; i++)
{
if (i > 0)
{
vector<int> seq2 = seq;
seq2.push_back(i);
if (direct == 0)
{
result += seqRun(N,M,K,L,run,0,seq2);
}
else
{
result += seqRun(N,M,K,L,run+1,0,seq2);
}
}
}
for (int i = last_val+1; i <= last_val+L; i++)
{
if (i <= K)
{
vector<int> seq2 = seq;
seq2.push_back(i);
if (direct == 1)
{
result += seqRun(N,M,K,L,run,1,seq2);
}
else
{
result += seqRun(N,M,K,L,run+1,1,seq2);
}
}
}
vector<int> seq2 = seq;
seq2.push_back(last_val);
result += seqRun(N,M,K,L,run,-1,seq2);
return result;
}
Use recursion, check the provide C++ code
static bool findPattern(char *str, int len, char** arr, int n, int m)
{
if (len <= 0)
return 0;
int i = 0, j = 0;
for (i = 0;i<5;i++)
for(j = 0;j<5;j++)
{
if (arr[i][j] == str[0])
{
cout << "found the first char\n";
return findPattern(str,len,0,arr,n,m,i,j);
}
}
return 0;
}
static bool findPattern(char *str, int len, int k, char** arr, int n, int m, int i, int j)
{
if (k < 0 || k >= len || i < 0 || j < 0 || i >= n || j >= m)
return 0;
if (arr[i][j] == str[k])
{
if (k == len-1)
return 1;
int sum = 0;
for (int r = -1; r <= 1; r++)
for (int t = -1; t <= 1; t++)
if (r!=0 || t!=0)
{
sum += (int)findPattern(str,len,k+1,arr,n,m,i+r,j+t);
}
return (sum>0);
}
return 0;
}
static void printCombination(int n)
{
string str;
printCombination(n, 1, str);
}
static void printCombination(int n, int current, string str)
{
if (n == 0)
{
cout << str << endl;
return;
}
for (int i = current; i <= n; i++)
{
char temp[10];
itoa(i,temp,10);
printCombination(n-i, i, str+string(temp));
}
}
It reminds me of an earlier question about binary search tree. The tentative answer is provided below.
bool comAncestor (Tree *tree) {
if (tree == null) { return false;}
if (comAncestor(tree->left) && comAncestor(tree->right)) {
cout << tree->value << " ";
}
return true;
}
merge sort. with linked list, the merge can be done with const space complexity
- Daru December 14, 2012