I fail to see how any of them work in the general case.
In fact, I don't even see them working with range restrictions for n. Also
what is the missing number you are talking about? The question is to find
the repeated number. As I said before, its an element uniqueness problem
whose lower bound
Let f(n) = n(n+1)/2
We have to find n1 and n2 such that f(n1) N = f(n2) and n2 = n1 + 1.
Solution is n2.
Can be done in O(1) as follows:
Solve N = n(n+1)/2 for unknown n.
Requires us to solve quadratic equation: n^2 + n - 2N = 0
Find positive root of the equation which could be a real number.
Node *flatten(Node *node) {
if (!node)
return NULL;
Node *head = node;
Node *next = node-next;
node-next = NULL;
if (node-down)
node-next = flatten(node-down);
while (node-next != NULL)
node = node-next;
node-next = flatten(next);
return head;
}
On Wed, Feb 16, 2011 at 8:38 PM, bittu
using namespace std;
int main(){
int n,ac,k,sum;
while(cinn n){
ac=0;
k=ceil((sqrt(1+8*n)-1)/2)-1;
ac+=k*(k+1)*(2*k+1)/6;
sum=(k+1)*(k+2)/2;
ac+=(k+1)*((k+1)-(sum-n));
coutn acendl;
}
}
2011/2/16 nphard nphard nphard.nph
This problem does not seem to have a O(n) time solution in the general case
because it is a version of the Element uniqueness problem (
http://en.wikipedia.org/wiki/Element_distinctness_problem) which has a
proven tight asymptotic bound of *n log n*.
On Sun, Jan 16, 2011 at 11:17 PM,
For len = 6, isn't bcbcbc also valid?
On Sun, Feb 6, 2011 at 9:08 PM, Anand anandut2...@gmail.com wrote:
There is a language with only two elements ie 'a' and 'bc'. How many words
can be
made out of it if whose Length is n.
I think it is n+1.
if the len = 3
abc
bca
if the len is 6
O(n) is impossible even for an array where we can do random access.
On Sun, Jan 30, 2011 at 11:39 AM, juver++ avpostni...@gmail.com wrote:
There is a well-known bound for the comparison sort, O(nlogn).
If there is a way to sort doubly-linked list in a linear time, so we are
able to sort all
, nphard nphard nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B
One more thing is that you cannot stop if you reach the goal state as you
still do not know if its the optimal path or not (heuristic does not help in
that). So, you need to search in a Breadth First manner anyway regardless of
reaching goal states in some places to determine the optimal path (as
are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote:
If you convert the given binary tree into right threaded binary
tree,
won't
you be using extra space while doing so? Either the given tree
should
already
we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.comwrote:
@Ritu - Do you
using
additional space(as successor of any node is available O(1) time) and
keep track of 5th largest element.
Regards,
Ritu
On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote:
Theoretically, the internal stack used by recursive functions must be
considered for space
:
No,no extra space is needed.
Right children which are NULL pointers are replaced with pointer to
successor.
On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote:
If you convert the given binary tree into right threaded binary
tree,
won't
you be using extra space
Theoretically, the internal stack used by recursive functions must be
considered for space complexity.
On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote:
internal stack != extra space
--
You received this message because you are subscribed to the Google Groups
Algorithm
I don't understand what you mean.
Consider a simple inorder traversal of a balanced binary tree. Using
recursion, the code is simply:
void inorder(Node *node) {
if (node == NULL)
return;
inorder(node-left);
print(node-val);
inorder(node-right);
}
What do you consider to be the above
O(n) is correct.
On Sun, Jan 16, 2011 at 6:04 AM, snehal jain learner@gmail.com wrote:
The running time of an algorithm is represented by the following
recurrence relation:
if n = 3 then T(n) = n
else T(n) = T(n/3) + cn
Which one of the following represents the time
Given an array of integers of size 'n' - consisting of 'n-2' unique integers
and 1 integer with a duplicate, find the repeated element in O(n).
Note: This is a converse of finding the unique element in an array
consisting of duplicates - which can be solved with the XOR technique - but
I am not
No.
On Sat, Jan 15, 2011 at 11:06 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
do you have the range of elements in the array?
On Sun, Jan 16, 2011 at 8:51 AM, nphard nphard nphard.nph...@gmail.comwrote:
Given an array of integers of size 'n' - consisting of 'n-2' unique
integers
A cool way of solving this is by using the suffix tree.
1. Concatenate the string with itself.
2. Create a suffix tree.
3. Descend along the least lexicographic path from the root.
Solution works in O(n).
On Jan 15, 4:55 pm, Jammy xujiayiy...@gmail.com wrote:
@Wei Please test you code on
19 matches
Mail list logo
