w.y
BAN USERHow about the tail-recursive way to try all possible combinations?
The time complexity would be O(n^2).
int findGenericKey(char *entered)
{
if (!entered)
return -1; // -1 means "failed to find the key"
int key = 0 ;
int i ;
int len = strlen(entered);
while (! KeyPad.pressKey(key)
&& i < len)
{
i++;
key = key * 10 + entered[i] - '0';
if (key < 0)
{
// assume the key be positive
// when it gets to negative, the value has been overflown
// no need to try more in this loop
break; // out of the while-loop
}
} // end of while
if ( key >= 0 // again assume the key is non-negative
&& KeyPad.pressKey(key))
return key ; // found the key
else
return findKey(entered + 1);
}
I think this is a typical dynamic programming question. Using following formula to get:
D[i] = D[i-1] + (A[i] - A[i-1])
D[0] = 0
Where A[] is the input array and D[] is the difference array that we calculate from input A[].
For example, A[] = 1, 5, 8, 7, 9, -5, 15, 21
Calculate D[] = 0, 4, 7, 6, 8, -6, 14, 20
go through D[] to find the maximum difference is 20, which is really O(n) complexity
This is impossible to solve it in O(n). Assume everyone is celebrity, i.e., nobody knows any one. In that case, you have to make (n-1)*(n-1) comparison, this is O(n^2) complexity. This is the worse case. The best case would be
- 1 knows 2, eliminate 1
- 2 knows 3, eliminate 2
- (n-1) knows n, eliminate (n-1)
this is the only corner case that would result in O(n). Otherwise, it will be between O(n) to O(n^2), thus O(n^2).
You can easily modify your code to restore its original matrix.
- w.y May 31, 2015