igor grudenic
BAN USER<pre lang="" line="1" title="CodeMonkey10275" class="run-this">Simple brute force would be to keep all the previous solutions and then iterate over
them to find the minimal one that multiplied by 2 or 5 gives the number greater
then the current element. History search should start at the latest number and continue by decreasing solutions until the first one found and multiplied by 5 is lesser then current element. Complexity is linear space, ant time is certainly better than O(n^2) but one should prove that limited history search is better than O(n) (and it is).
void GetElementsSimple(int n){
list<int> solutions;
int curSolution;
int bestNext;
solutions.push_back(1);
while(n){
curSolution=solutions.back();
cout<<solutions.back()<<" ";
bestNext=curSolution*2;
for(list<int>::reverse_iterator i=solutions.rbegin();
i!=solutions.rend()&& (*i)*5>curSolution;
i++){
if(((*i)*5>curSolution)&&((*i)*5<bestNext)) bestNext=(*i)*5;
if(((*i)*2>curSolution)&&((*i)*2<bestNext)) bestNext=(*i)*2;
}
solutions.push_back(bestNext);
n--;
}
}
Additionally one may try to exercise O(n) solution that takes a numeber 2^i*5^j
and tries to create 2 exchanges. First is to convert a subset of 2^i to 2^(i-n)*5^n. The second is to convert 5^j to 2^m*5^(j-m). Conversion that gets smaller solution must be used.
Optimal conversion for all parameters i and j can be precomputed. This leads to provable O(n) time after precomputation.
</pre><pre title="CodeMonkey10275" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey59148" class="run-this">char* LongestPrefix(char **strings,int n){
int i,prefixLength,zeroLength;
char *result;
zeroLength=strlen(strings[0]);
for(prefixLength=0;prefixLength<zeroLength;prefixLength++){
for(i=1;i<n;i++){
if((strings[i][prefixLength]==0)||
(strings[i][prefixLength]!=strings[0][prefixLength]))
break;
}
if(i<n) break;
};
result=(char *)malloc(sizeof(*result)*(prefixLength+1));
strncpy(result,strings[0],prefixLength);
result[prefixLength]=0;
return result;
}</pre><pre title="CodeMonkey59148" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey85370" class="run-this">I think this one can be somewhere between linear and n^2. Algorithm goes recursively and it looks into 2 pointers t1 and t2. Suppose t1->data < t2->data. If that holds then children of t1 and t2 point to data that belong to following subsets:
t1->left [-MAXINT,t1->data]
t1->right [t1->data+1,t2->data] U <t2->data,MAXINT]
t2->left [-MAXINT,t1->data] U <t1->data,t2->data]
t2->right <t2->data,MAXINT>
So basically we have to make following recursive calls
...
function(t1->left,t2->left) but limited to print numbers from [-MAXINT,t1->data]
cout<<t1->data;
function(t1->right,t2->left) but limited to print numbers from <a,t2->data]
cout<<t2->data;
function(t1->right,t2->right) but limited to print numbers from <t2->data,MAXINT]
What is the complexity of the solution? Well, for pair of nodes on the top level we create 3 recursive calls on topLevel+1. This leads to 3^level complexity. Since level is log2(n) we have 3^(log2(n))=n^(log2(3))=n^1.5849.
This can be improved by preventing recursive calls on subtrees than do not meet limits requirements, but analysis of this would be much more complicated then I am willing to do at the moment :-).
The entire code for the routine is here:
static void printSorted2TreesInternalNew(
TreeNode *t1,
TreeNode *t2,
int min,
int max){
if((t1==NULL)&&(t2==NULL)) return;
if(t1==NULL)
swapTreePointers(t1,t2);
if(t2==NULL){
printSorted2TreesInternalNew(t1->left_,t2,min,max);
std::cout<<t1->data_<<" ";
printSorted2TreesInternalNew(t1->right_,t2,min,max);
return;
}
if(t2->data_<t1->data_)
swapTreePointers(t1,t2);
printSorted2TreesInternalNew( t1->left_,
t2->left_,
min,
std::min(max,t1->data_));
if((t1->data_>min)&&(t1->data_<=max))
std::cout<<t1->data_<<" ";
printSorted2TreesInternalNew( t1->right_,
t2->left_,
std::max(min,t1->data_),
std::min(max,t2->data_));
if((t2->data_>=min)&&(t2->data_<=max))
std::cout<<t2->data_<<" ";
printSorted2TreesInternalNew( t1->right_,
t2->right_,
std::max(min,t2->data_),
max);
}
Of course you have to call it with min and max set to int range.
</pre><pre title="CodeMonkey85370" input="yes">
</pre>
Repevelynleary0, Consultant at Arista Networks
Hi, I am Evelyn from Los Angeles, USA. I have been a Marketing Manager in Veramons Digital Company from last ...
RepJe suis Kirsten. Je travaille dans un magasin en tant que responsables de la chaîne d'approvisionnement pour promouvoir la ...
RepI am Risk managers that advise organizations on any potential risks to the profitability, safety, security or existence of the ...
Repclarasbarr, Korean Air Change Flight at Adap.tv
I am ClaraBarr from California USA. Writes and records various different genres for television, film and other artists.Wrote several ...
Repsharoneruther, AT&T Customer service email at ABC TECH SUPPORT
I am Sharon, from Bethlehem USA. I am working as a Park naturalist in Sammy's Record Shack company. I ...
Repgradyjvierra, Animator at Alliance Global Servies
Je suis Grady de Phoenix USA. Je travaille en tant que technicien de laboratoire clinique dans la société Samuels Men ...
RepLizzieGibson, Cloud Support Associate at Aspire Systems
I'm an engineering student from Huntsville, AL USA. Have more interest in management and stuff related to business. Promptly ...
RepSoccer lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
RepShirleyMHansen, Project Leader at Chelsio Communications
I am Physical Therapy Aide with 3 years experience in hospital. I like to build up my knowledge of various ...
Repshirleygause93, Analyst at Absolute Softech Ltd
Hi, I am Shirley from taxes, Conducted a re-profiling project which enabled our customers to receive orders more efficiently.Planning ...
Repmelissamewingm, abc at ABC TECH SUPPORT
I am Melissa from Springdale. I function as an Auditing assistant in Bountiful Harvest Health Food Store. My solid interest ...
RepVirginiaSlifer, Analyst at A9
In my professional life, I am a dedicated genetics nurse with a deep interest in understanding the intricacies of human ...
RepFannieRamirez, Accountant at A9
I am a technically skilled Payroll bookkeeper responsible for the full charge bookkeeping function. My expertise includes knowledge of accepted ...
RepBonnieToney, abc at A9
I am a highly dedicated and accomplished asset manager with an exceptional work ethic and customer service record. I adapt ...
Replisachndi, Backend Developer at Adjetter Media Network Pvt Ltd.
I am the manager of health services. I work in managing medical and health services in hospitals, community health institutions ...
There is a recursive way to find all the solutions:
TrieNode is a node in a prefix tree. Node has a wordMark field that denotes whether set of
- igor grudenic December 08, 2011characters formed by visiting all the parent nodes in a tree constitute a valid word.
Method call newNode=oldNode.moveForward(c) returns new trie node reachable from oldNode
using character c.
Complexity of finding one solution is by O(N*C) (N-sentence length, C-lenght of the longest
dictionary word). Complexity of moveForward(c) is O(1).
Number of solutions may vary greatly depending on a sentence length and size of the
dictionary. For instance if one uses Morse alphabet the number of valid sentences may easily
become exponential.