javierturek
BAN USERCounting the number of subsequences is O(n^2) in the general case as well.
If you assume non-negative values in the array or a sorted array then O(n) is achievable.
Where do banks pay simple interest?!
- javierturek January 30, 2014Thanks for point out the error. I have updated the algorithm.
The idea is simple. Count how many times does every number appear in every position using the most significant digits and using the least significant digits and itself.
The 0 should be corrected as it could not be the most significant digit.
For example:
n = 209
for the units:
0 to 9 will appear 20 times (from 00 to 19 inclusive) + 1 more time for 20
for the tens:
0 to 9 will appear 2 times * 10 (from 0 to 1 inclusive) + (9+1) more times for 0
for the hundreds:
0 to 9 will appear 0 times * 100 (from 0 to 0) + 1 more time *100 for 0 and 1 - 100 for 0 + (9+1) times for 2
If you want from k to n , then count from 0 to n and remove the 0 to k part from the array of buckets.
If you need to take into account negative numbers, then add from -m to 0 (doing 0 to m).
The solution is simpler than iterating from 0 to n and counting the digits:
This solution is O(log n) instead of O(n).
void countDigits(int n)
{
int digits[10], j, multiplier = 1, m=n;
for (j=0; j< 10; j++)
digits[j] = 0;
if (n == 0) // Edge case: n is 0
digits[0] = 1;
while (n>0)
{
int current = n % 10;
for (j=0;j<10;j++)
digits[j] += (n /10) * multiplier + (j < current)*multiplier;
digits[current] += (m % multiplier)+1;
if (multiplier > 1)
digits[0] -= multiplier;
n /= 10;
multiplier *= 10;
}
for (j=0; j<10; j++)
printf("digits[%d]=%d\n",j,digits[j]);
}
I agree here. And this solution would be O(n^2).
- javierturek January 22, 2014
Sorting won't work. If you look at 4, 5, 6, 7
- javierturek October 13, 2014Sorting will give you a cost of 9 + 15 + 22 = 46
Huffman/minheap above will give you a cost of 9 + 13 + 22 =44
In the example 1,9,6,2,5, the minheap algorithm will do the following steps:
1 with 2, cost 3
3 with 5, cost 8
6 with 8, cost 14
9 with 14, cost 23
which is 48 overall.