Re: [algogeeks] zig zag problem
@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 lastIndex=0; toggle=arr[i+1] arr[i]; flag1=toggle; flag2=!flag1; if(len = 2) { return 0; } for(i=0;ilen;i++) { if(i==len-1) { break; } if(toggle==1) { if(arr[i+1] arr[i] arr[lastIndex] arr[i+1] flag1==1) { subseq++; flag1=0; flag2=1; toggle=0; lastIndex=i+1; } printf(\n\nin toggle = 1); printf(\n i = %d , lastIndex = %d , subseq = %d,i,lastIndex,subseq); } else { if(arr[i] arr[i+1] arr[lastIndex] arr[i+1] flag2==1) { subseq++; flag2=0; flag1=1; toggle=1; lastIndex=i+1; } printf(\n\nin toggle = 0); printf(\n i = %d , lastIndex = %d , subseq = %d,i,lastIndex,subseq); } } return subseq; } int main() { int arr[80],i,j,n,ls=1; printf(\nNumber of elements to be entered = ); scanf(%d,n); for(i=0;in;i++) { printf(\nEnter Number = ); scanf(%d,arr[i]); } ls=findSeqLen(arr,n,ls); printf(\n\nSubsequence len = %d\n\n,ls); } On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg ankurga...@gmail.com wrote: @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 as 4 whereas in the answer should be 3 Regards Ankur On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg ankurga...@gmail.com wrote: 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++){ if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){ DP[i][0]=DP[i-1][0]; DP[i][1]= i-1; } if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){ DP[i][0]=DP[i-1][0]+1; DP[i][1]= i-1; } else{ j = DP[i-1][1]; while(j0){ if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){ DP[i][0]=max(DP[j][0]+1,DP[i-1][0]); if(DP[i][0]==DP[j][0]+1) DP[i][1]=j ; else DP[i][1]= i-1; break; }else j= DP[j][1]; } if(j==0){ DP[i][0]=DP[i-1][0]; DP[i][1]=DP[i-1][1]; } } } return DP[n-1][0]; } On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote: 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.comwrote: 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; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote: 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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this
Re: [algogeeks] zig zag problem
@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 take the first element of sign change and we can take last element. 14327862 so answer should be 1 4 2 8 2 correct me if i am wrong On Mon, Dec 19, 2011 at 12:26 PM, atul anand atul.87fri...@gmail.comwrote: @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 lastIndex=0; toggle=arr[i+1] arr[i]; flag1=toggle; flag2=!flag1; if(len = 2) { return 0; } for(i=0;ilen;i++) { if(i==len-1) { break; } if(toggle==1) { if(arr[i+1] arr[i] arr[lastIndex] arr[i+1] flag1==1) { subseq++; flag1=0; flag2=1; toggle=0; lastIndex=i+1; } printf(\n\nin toggle = 1); printf(\n i = %d , lastIndex = %d , subseq = %d,i,lastIndex,subseq); } else { if(arr[i] arr[i+1] arr[lastIndex] arr[i+1] flag2==1) { subseq++; flag2=0; flag1=1; toggle=1; lastIndex=i+1; } printf(\n\nin toggle = 0); printf(\n i = %d , lastIndex = %d , subseq = %d,i,lastIndex,subseq); } } return subseq; } int main() { int arr[80],i,j,n,ls=1; printf(\nNumber of elements to be entered = ); scanf(%d,n); for(i=0;in;i++) { printf(\nEnter Number = ); scanf(%d,arr[i]); } ls=findSeqLen(arr,n,ls); printf(\n\nSubsequence len = %d\n\n,ls); } On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg ankurga...@gmail.com wrote: @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 as 4 whereas in the answer should be 3 Regards Ankur On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg ankurga...@gmail.comwrote: 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++){ if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){ DP[i][0]=DP[i-1][0]; DP[i][1]= i-1; } if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){ DP[i][0]=DP[i-1][0]+1; DP[i][1]= i-1; } else{ j = DP[i-1][1]; while(j0){ if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){ DP[i][0]=max(DP[j][0]+1,DP[i-1][0]); if(DP[i][0]==DP[j][0]+1) DP[i][1]=j ; else DP[i][1]= i-1; break; }else j= DP[j][1]; } if(j==0){ DP[i][0]=DP[i-1][0]; DP[i][1]=DP[i-1][1]; } } } return DP[n-1][0]; } On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote: 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.comwrote: 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; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote: 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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is
Re: [algogeeks] zig zag problem
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 ; ilen ;i++) { if ( toggle == 1) { if( arr[i+1] arr[i]) { subseq=subseq+2; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote: 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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] zig zag problem
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++){ if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){ DP[i][0]=DP[i-1][0]; DP[i][1]= i-1; } if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){ DP[i][0]=DP[i-1][0]+1; DP[i][1]= i-1; } else{ j = DP[i-1][1]; while(j0){ if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){ DP[i][0]=max(DP[j][0]+1,DP[i-1][0]); if(DP[i][0]==DP[j][0]+1) DP[i][1]=j ; else DP[i][1]= i-1; break; }else j= DP[j][1]; } if(j==0){ DP[i][0]=DP[i-1][0]; DP[i][1]=DP[i-1][1]; } } } return DP[n-1][0]; } On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote: 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.comwrote: 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; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote: 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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] zig zag problem
@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 as 4 whereas in the answer should be 3 Regards Ankur On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg ankurga...@gmail.com wrote: 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++){ if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){ DP[i][0]=DP[i-1][0]; DP[i][1]= i-1; } if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])0){ DP[i][0]=DP[i-1][0]+1; DP[i][1]= i-1; } else{ j = DP[i-1][1]; while(j0){ if((a[i]-a[j])*(a[j]-a[DP[j][1]])0){ DP[i][0]=max(DP[j][0]+1,DP[i-1][0]); if(DP[i][0]==DP[j][0]+1) DP[i][1]=j ; else DP[i][1]= i-1; break; }else j= DP[j][1]; } if(j==0){ DP[i][0]=DP[i-1][0]; DP[i][1]=DP[i-1][1]; } } } return DP[n-1][0]; } On Sun, Dec 18, 2011 at 11:04 AM, atul anand atul.87fri...@gmail.comwrote: 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.comwrote: 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; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.comwrote: 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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] zig zag problem
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; } toggle=0; } else { if(arr[i] arr[i+1]) { subseq=subseq+2; } toggle=1; } } print subseq; On Fri, Dec 16, 2011 at 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. 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 example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] zig zag problem
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 zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] zig zag problem
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. 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 example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.