@Ankur :
yeah rite it wont work i have modified my algo and used many test cases
, it is giving rite output.
could you catch any test case for which it would fail.
here is the updated code :-
#includestdio.h
int findSeqLen(int arr[],int len,int subseq)
{
int i=0,flag1,flag2,toggle;
int
@UTKARSH :
it should be 1 4 3 7 6
why are you skipping 3 even when 143 is in zig zag sequence.
On Tue, Dec 20, 2011 at 11:26 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com
wrote:
hi i want to know whether this is right
suppose array is : 1,4,3,2,7,8,6,2
we just find where sign changes and
complexity of this algo is O(n) ..I guess it is better than dynamic
programming approach which is O(n^2).
On Sat, Dec 17, 2011 at 6:28 PM, atul anand atul.87fri...@gmail.com wrote:
please see the algo and let me know if i am doing it wrong:-
toggle= arr[i+1] arr[i];
subseq=0;
for( i=0 ;
a linear solution for this problem . although its more than O(n) but will
never be O(n*2)..used DP to solve it
space used -O(2n)
int ZigZagLength(vectorint a){
int n=a.size();
int DP[n][2];
DP[0][0]=1;
DP[0][1]=0;
DP[1][0]=2;
DP[1][1]=0;
int j;
for(int i=2;in;i++){
@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer
please see the algo and let me know if i am doing it wrong:-
toggle= arr[i+1] arr[i];
subseq=0;
for( i=0 ; ilen ;i++)
{
if ( toggle == 1)
{
if( arr[i+1] arr[i])
{
subseq=subseq+2;
}
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
It is dynamic programming.
Search in topcoder algo tutorials
On Dec 16, 2011 10:33 AM, Sangeeta sangeeta15...@gmail.com wrote:
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative.
only possible for continuous disctees attributes.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Print tree in zig zag manner
1
/ \
23
/ \ / \
4 56 7
O/P: 1 3 2 4 5 6 7
--
Regards,
Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
You can use two stacks(A, B) when traversal.
Use A as the stack when traveling the odd levels.
B as the even levels.
A.push(1);
A.pop(); //1
//push the son of the node 1, from left to right;
B.push(2);
B.push(3);
B.pop(); // 3
//push the son of the node 3, from right to left
A.push(7);
use one queue
Enqueue all the nodes in normal level order traversal in the queue
as 1 2 3 4 5 6 7
Each level contains 2 to the power n nodes in the queue.
have two pointers ptr1 and ptr2
point ptr1 to the start node of 2 power n nodes range and ptr2 to the last
node of this range.
For odd
How about this dp solution?
Let dp[i][j][k] be the lookup table.
It is defined as the longest zigzag sequence in the range i and j. k is
either 0 or 1.
0- if the sequence ends with a positive difference, i.e last element is
greater than the last to one.
1- if the sequence ends with a negative
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
zig-zag sequence.
For
See Topcoder Dynamic Programming Tutorials :)
On Fri, Jan 21, 2011 at 12:48 PM, snehal jain learner@gmail.com wrote:
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if
Please help me to write the following algorithm:
Call a sequence of integers a zig-zag sequence if the differences between
successive numbers strictly alternate between positive and negative (for
example, 5, 7,3,9,-1,4,3,6,0). The first difference may be either positive
or negative. Given a
16 matches
Mail list logo
