jyimmer
BAN USERLast update. I went ahead and tested the code and it works. Once again the final solution is:
/* if pos is currently less than most significant digit */
if (b/pos > 0) {
return findMostSigDig(b, pos, pos*pos);
}
/* if pos is currently at one position greater than the most significant digit*/
if (b/(pos/10) > 0) {
return pos;
}
/* if we have overshot pos, recurse with smaller subset */
return findMostSigDig(b / prev, 1, 10) * prev;
Hi all. I see a lot of O(n) solutions but this problem can actually be solved in O(log n) time.
public int concatInts (int a, int b) {
return a * findMostSigDig(b, 10) + b;
}
/* Notice in this following method, I am not iterating through b linearly but exponentially therefore you get a log n solution */
public int findMostSigDig (int b, int prev, int pos) {
/* if pos is currently less than most significant digit */
if (b/pos > 0) {
return findMostSigDig(b, pos, pos*pos);
}
/* if pos is currently at one position greater than the most significant digit
if (b/(pos/10) > 0) {
return pos;
}
/* if we have overshot pos, recurse with smaller subset */
return findMostSigDig(b / prev, 1, 10) * prev;
}
This code has NOT been tested and can be full of bugs but this is the general idea. Solution may change depending on whether negatives are allowed or what the range of ints are.
- jyimmer January 06, 2014
I wrote a O(log n) algorithm below where n is the number of digits in int b.
- jyimmer January 07, 2014