sameerBandla
BAN USERSimple solution which takes O(cuberoot(A)) space and similar time. Precompute the cubes and then do one pass to find out how many pairs add to A.
bool IsPresent(UINT A, UINT N)
{
vector<UINT> cubes;
for (UINT i=1; i < A; i++)
{
UINT cube = i*i*i;
if (cube < A)
{
cubes.push_back(cube);
}
else
{
break;
}
}
UINT min=0, max = cubes.size() -1, count=0;
while ( (min < max) && (count < N))
{
if (cubes[min] + cubes[max] < A)
{
min++;
}
else if (cubes[min] + cubes[max]== A)
{
count ++;
min++;
max--;
}
else
{
max--;
}
}
return (count ==N);
}
For a fixed input, median can be found in O(n) time if you can modify the array. See Selection_algorithm in wikipedia.
- sameerBandla February 16, 2013No - heap takes O(logm) for comparison not O(m). Look at the solution I gave
- sameerBandla January 09, 2013Here is the code:
class mycomparison
{
public:
bool operator() (const pair<int,int> & lhs,
const pair<int,int> & rhs)
{
return lhs.first > rhs.first;
}
};
vector<int> MergeMatrix(int input[M][N])
{
priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pq;
vector<int> result;
vector<int> current(M, 0);
for (int i=0; i < M; i++)
{
pair<int,int> value;
value.first = input[i][0];
value.second = i;
pq.push(value);
current[i]=0;
}
while (! pq.empty() )
{
pair<int,int> top;
top = pq.top();
pq.pop();
if (result.size() ==0)
{
result.push_back(top.first);
}
else if (result[result.size()-1] != top.first)
{
result.push_back(top.first);
}
if (current[top.second] < N-1)
{
current[top.second]++;
top.first = input[top.second][current[top.second]];
pq.push(top);
}
}
return result;
}
this will be O(mn)log(mn) and also needs an extra O(mn) space
- sameerBandla January 08, 2013Since each of the m rows are sorted, all you need to do is to do a m-way comparison to find the minimum element from the m rows. You can ignore duplicates since you know the previous minimum. This will give an O(mn*m) algorithm since there are m comparisons at each step.
However, the m-way comparison at each step to find the minimum can be done using a heap - which will give us an O(mn*logm) algorigm with only O(m) extra memory.
Here is a solution with DP and recursion. At each level of the recursion, fix the value of one dice.
- sameerBandla April 29, 2013