Pyramid
BAN USERDo you mean that within each `if (charArray[readPos] >= lower && charArray[readPos] <= upper)` branch, the sub-array is only shifted by one unit? If so, then, true, only constant time is used. However, in the worst case, \Theta(n) elements will be shifted for \Theta(n) times. Hence the time complexity might be O(n^2). Anyway, the code above does not seem to be a worst case O(n) algorithm.
- Pyramid August 30, 2015The space complexity is not constant. The difference between writePos and readPos might be O(n), hence the arraycopy method needs O(n) space. Moreover, you used arraycopy only for once within each scan, which probably "covers" some elements. I think to ensure no char/element is lost, one should use swap or copying twice.
- Pyramid August 28, 2015I don't think this is a correct algorithm. The existence of space is not a problem, we can solve it by metamorphosing-and-restoring method.
This algorithm claims iteration1->iteration2->iteration1.
Suppose we have a string 5ABcd, where 5 represents space.
Iteration 1: after the 1st swap, cAB5d; after the 2nd swap, cABd5.
Iteration 2: after the 1st swap, cA5dB; after the 2nd swap, c5AdB.
Iteration 1: after the 1st swap, cdA5B.
The result is incorrect. Of course we can perform iteration 2 again. But this is only for a simple example. For longer and more complex string, the repeat times will increase.
Actually, I suspect if there exists a O(n) time O(1) space algorithm
The OP provided a link which is supposed to be identical to the interview problem. The following code solves the problem in HackerRank.
Linear (time,space) complexity. Two memoir arrays are used for two stairs respectively.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T = 0;
int N, K, P;
int *A, *B, *PA, *PB; // PA[i]: minimum total penalty after arriving at A[i]
int costAA=999999, costAB=999999, costBA=999999, costBB=999999;
cin >> T;
for (int testIndex=0; testIndex<T; testIndex++)
{
costAA=999999, costAB=999999, costBA=999999, costBB=999999;
cin >> N >> K >> P;
A = new int [N]; B = new int [N];
PA = new int [N]; PB = new int [N];
for (int i=0; i<N; i++)
cin >> A[i];
for (int i=0; i<N; i++)
cin >> B[i];
if (K>=N)
{
costAA = A[0]+A[N-1];
costBB = B[0]+B[N-1];
costAB = A[0]+B[N-1]+P;
costBA = B[0]+A[N-1]+P;
costAA = min(costAA,costBB);
costAA = min(costAA,costAB);
costAA = min(costAA,costBA);
cout << costAA << '\n';
}
else
{
PA[N-1] = A[N-1]; PB[N-1] = B[N-1];
for (int i=1; i<=K; i++)
{
PA[N-1-i] = A[N-1-i]+min(P+PB[N-1],PA[N-1]);
PB[N-1-i] = B[N-1-i]+min(P+PA[N-1],PB[N-1]);
}
for (int i=N-1-K-1; i>=0; i--)
{
costAA=costAB=costBA=costBB=999999;
for (int step=1; step<=K; step++)
{
costAA = min(costAA,PA[i+step]);
costBB = min(costBB,PB[i+step]);
costAB = min(costAB,PB[i+step]);
costBA = min(costBA,PA[i+step]);
}
PA[i] = min(costAA,costAB+P)+A[i];
PB[i] = min(costBB,costBA+P)+B[i];
}
cout << min(PA[0],PB[0]) << '\n';
}
delete [] A; delete [] B;
delete [] PA; delete [] PB;
}
return 0;
}
I haven't work it out yet, but got some idea. Hope someone could help me move forward from this point.
Observation1: for any two integers grater than one, their product is no smaller than their summation. And the product is equal to the summation iff the two integers are both two.
Observation2: for any positive integer X, (X+1)>X*1
Hence in the sequence, for any two consecutive non-one integers, * should be inserted rather than +.
Allowing sorting makes the maximum different (and easier): (1,3,1) vs (1,1,3). We assume that the original order should be kept.
So + and () are only involved when 1 appears.
For the case a,b,1,c,d, where a,b,c,d are greater than one, we should add 1 with min(b,c).
For the case ..,1,a,1,b,1,c,.. what shall we do?
For sequence 1,1,...,1,1, we know from arithmetic that splitting them equally could get maximum product. Assume we partition them into k groups, we'd like to maximize function (n/k)^k, calculus suggests that k=n/e achieves maximum. So we only need to try k=ceil(n/e) and k=floor(n/e). Eg. for [1]*10, n=10, k=3,4. for k=3, we have (3*3*4=36); for k=4, we have (2*2*3*3=36);
For sequence ..,a,1,1,...,1,1,b,.. what shall we do?
Thanks for user smarthbehl sharing this problem. I believe I came up with a linear time constant space solution. Due to code complexity, my code uses recursive, hence it has stack space overhead. But one can convert it into a non-recursive one and get a constant space solution.
Assume elements are distinct. otherwise there may or may not be a problem.
pseudo-code:
median <- quickSelection(A); // linear time, A is bi-partitioned such that A[left elements]<A[medianIndex]=median<A[right elements];
while (leftPointer < medianIndex)
swap(A[leftPointer],A[rightPointer]);
leftPointer+=2; rightPointer-=2;
end;
code:
- Pyramid September 03, 2015