Re: [algogeeks] Re: Sort array with two subparts sorted
But Vaibhav's solution I think is O(n^2). For example, when input is 101 102 103 104 1 2 3 4 We first swap 1 and 101 and then bubble 101 to the end of the subarray 2 3 4 . This bubbling we must repeat after each swap. This results in n/2 + n/2-1 + n/2-2 + .. comparisons, which is O(n^2). Please correct me if I am wrong. Can this be solved in better than O(n^2) with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 8:43 PM, Carl Barton odysseus.ulys...@gmail.comwrote: That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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] Re: Sort array with two subparts sorted
Okay, forgetting the information that two parts are sorted and treating it as any other array, we can sort in O(nlogn) using, say, heapsort. Is O(n) possible with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 9:25 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote: But Vaibhav's solution I think is O(n^2). For example, when input is 101 102 103 104 1 2 3 4 We first swap 1 and 101 and then bubble 101 to the end of the subarray 2 3 4 . This bubbling we must repeat after each swap. This results in n/2 + n/2-1 + n/2-2 + .. comparisons, which is O(n^2). Please correct me if I am wrong. Can this be solved in better than O(n^2) with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 8:43 PM, Carl Barton odysseus.ulys...@gmail.comwrote: That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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] Re: Median of Binary Tree
Hi,
This is one approach to it:
1) Go to the first node in inorder traversal. Let the pointer be LP.
(Push the intermediate nodes to Lstack while doing this )
2) Go to the last node in inorder traversal. Let the pointer be RP.
(Push the intermediate nodes to Rstack while doing this )
while(LP-data RP-data){
LP = inordersuccessor(LP,Lstack)
// gets inorder successor and modifies Lstack accordingly
RP = inorderpredecessor(RP,Rstack)
// gets inorder predecessor and modifies Rstack accordingly
Lprev = LP
Rprev = RP;
}
if(LP-data = RP-data){ // even number of elements
retrun LP-data;
}else{
return Lprev-data + Rprev-data / 2
}
Time: O(n)
Memory: 2 * O ( log n) average
Thanks,
Balaji.
On Sun, Mar 27, 2011 at 7:17 PM, bittu shashank7andr...@gmail.com wrote:
@all
wake up geeks
Thanks
Shashank
--
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] Re: Median of Binary Tree
while(LP-data RP-data){
The condition is wrong and would work only for BST. We could probably change
it to
while(LP != RP Lprev != RP)
Thanks,
Balaji.
On Sun, Mar 27, 2011 at 8:03 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote:
Hi,
This is one approach to it:
1) Go to the first node in inorder traversal. Let the pointer be LP.
(Push the intermediate nodes to Lstack while doing this )
2) Go to the last node in inorder traversal. Let the pointer be RP.
(Push the intermediate nodes to Rstack while doing this )
while(LP-data RP-data){
LP = inordersuccessor(LP,Lstack)
// gets inorder successor and modifies Lstack accordingly
RP = inorderpredecessor(RP,Rstack)
// gets inorder predecessor and modifies Rstack accordingly
Lprev = LP
Rprev = RP;
}
if(LP-data = RP-data){ // even number of elements
retrun LP-data;
}else{
return Lprev-data + Rprev-data / 2
}
Time: O(n)
Memory: 2 * O ( log n) average
Thanks,
Balaji.
On Sun, Mar 27, 2011 at 7:17 PM, bittu shashank7andr...@gmail.com wrote:
@all
wake up geeks
Thanks
Shashank
--
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] Need help regarding the SPOJ problem...
Hi, I hope this is correct. Please correct if I am wrong. Short answer: Let a = (k-n)/(n-1) Let b = (k-n)%(n-1) steps = (n-1)(a)(a+1)/2 + b Put = steps + n Remove = steps Explanation: Example with n = 3 k =10: Start by putting balls in 1,2,3 1 2 3 x x x x x x Now move balls from 1-3 to 3-5 using (n-1) steps 1 x 3 4 x x x x x REMOVE 2, PUT 4 x x 3 4 5 x x x x REMOVE 1, PUT 5 Moving balls from 3-5 to 5-7 using steps 1 and 2. 1) move first n-1 balls to 1 to n -1 slots. This takes ( reached_so_far - n ) steps x x 3 4 5 x x x x REMOVE 4, PUT 2 x 2 3 x 5 x x x x REMOVE 3, PUT 1 1 2 x x 5 x x x x 2) move balls in 1 to n-1 slots to (reached_so_far + 1) to (reached_so_far + n -1) slots. This takes (n-1) steps 1 2 x x 5 x x x x REMOVE 2, PUT 6 1 x x x 5 6 x x x REMOVE 1, PUT 7 x x x x 5 6 7 x x Similarly we can move from 5-7 to 7-9 in ( 4 + 2 = 6 steps ) Now we can directly complete with one more step. Summary: Move from 1-3 to 3-5 in 2 steps Move from 3-5 to 5-7 in 4 steps Move from 5-7 to 7-9 in 6 steps Move 1 ball to 10 in 1 step PUT = 13(steps) + 3 (initial) REMOVE = 13(steps) Thanks, Balaji. On Fri, Mar 18, 2011 at 7:06 PM, shubham shubh2...@gmail.com wrote: You have N marbles and K slots. You have to follow the below mentioned rules : 1. You can put in a marble or take out a marble from slot numbered 1 at any time. 2. You can put in a marble or take out a marble from slot numbered i only if there exists a marble at the slot i - 1. 3. The game stops when a marble reaches the slot numbered K for the first time. Your task is to finish the game in minimum number of valid moves. for further clarification one can visit: http://www.spoj.pl/problems/MOVMRBL/ I am not able to calculate manually the steps for some (N,K) pair (except the cases where K is less than or equal to N*(N-1)/2). e.g how to proceed with just 3 marbles and 10 slots... any idea in this direction will be appreciated... -- 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] Re: Link list Problem
Also useless if what is given is the pointer to the last node, in which case the next pointer of last but one node will only remain dangling. Thanks, Balaji. On Wed, Mar 16, 2011 at 7:31 PM, Gene gene.ress...@gmail.com wrote: I think Wirth mentions this idea in Algorithms + Data Structures = Programs, which dates from the 70's. Of course this technique is useless if other pointers to the deleted note can exist. -- 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] linked list
1) You can use void* as the data part and then allocate memory separately
and use.
struct node
{
void* dataPtr;
struct node* next;
};
2) or Use embeddable lists:
http://isis.poly.edu/kulesh/stuff/src/klist/
Thanks,
Balaji.
On Wed, Mar 16, 2011 at 8:27 PM, himanshu kansal
himanshukansal...@gmail.com wrote:
can nodes of linked list in c/c++ contain different types of
datameans suppose 1st node of the list contains an integer value,
2nd contains a float,3rd has a string and so on..
--
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] Spoj Problem
It fails for input 1,2,3. I think there needs to be one more iteration to
check if the candidate is actually a majority element or not.
Thanks,
Balaji.
On Tue, Mar 15, 2011 at 9:50 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
CAN ANYONE PLEASE TELL ME WHY MY CODE IS GIVING WRONG ANSWER OR SOMEONE WHO
HAS GOT AC IN THIS PROBLEM MAY POST HIS SOLUTION
#includestdio.h
main()
{
long long int n,t,r,count,major,i;
scanf(%lld,t);
while(t--)
{
scanf(%lld,n);
scanf(%lld,r);
major=r;
count=1;
for(i=1;in;i++)
{
scanf(%lld,r);
if(r!=major)
{
count--;
if(count0)
{count=1;
major=r;
}
}
else
{
count++;
}
}
if(count=0)
printf(NO\n);
else
printf(YES%lld\n,major);
}
return 0;
}
--
*UTKARSH SRIVATAV*
*CSE-3
B-Tech 2nd Year
@MNNIT ALLAHABAD*
--
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] Spoj Problem
http://www.spoj.pl/problems/MAJOR/
http://www.spoj.pl/problems/MAJOR/Thanks,
Balaji.
On Tue, Mar 15, 2011 at 11:00 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
hey link to the problem??
On Tue, Mar 15, 2011 at 10:50 PM, Balaji Ramani rbalaji.psgt...@gmail.com
wrote:
It fails for input 1,2,3. I think there needs to be one more iteration to
check if the candidate is actually a majority element or not.
Thanks,
Balaji.
On Tue, Mar 15, 2011 at 9:50 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.com wrote:
CAN ANYONE PLEASE TELL ME WHY MY CODE IS GIVING WRONG ANSWER OR SOMEONE
WHO HAS GOT AC IN THIS PROBLEM MAY POST HIS SOLUTION
#includestdio.h
main()
{
long long int n,t,r,count,major,i;
scanf(%lld,t);
while(t--)
{
scanf(%lld,n);
scanf(%lld,r);
major=r;
count=1;
for(i=1;in;i++)
{
scanf(%lld,r);
if(r!=major)
{
count--;
if(count0)
{count=1;
major=r;
}
}
else
{
count++;
}
}
if(count=0)
printf(NO\n);
else
printf(YES%lld\n,major);
}
return 0;
}
--
*UTKARSH SRIVATAV*
*CSE-3
B-Tech 2nd Year
@MNNIT ALLAHABAD*
--
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.
--
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] Link list Problem
Copy contents of the next node to current node and delete the next node. Thanks, Balaji. On Sun, Mar 13, 2011 at 10:23 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: hi Given a singly Link list but Head of the List is unknown so my question is that How to delete a given node from the List??? -- 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] spoj problem
Find the gcd of n-1 differences ( a[1]..a[n-1] with a[0] ) ans = (a[n-1] - a[0])/gcd - n + 1 Thanks, Balaji. On Sat, Mar 12, 2011 at 2:00 PM, Akshata Sharma akshatasharm...@gmail.comwrote: Any faster way to solve this problem?? On 3/12/11, Balaji Ramani rbalaji.psgt...@gmail.com wrote: Yes, the correct answer is 0. if(flag ==0 || ans ==0) i think can be changed to if(flag ==0) alone. Thanks, Balaji. On Sat, Mar 12, 2011 at 10:16 AM, Satyam Kapoor satyamkapoo...@gmail.comwrote: is case main answer 0 hona chahiye. -- Satyam Kapoor B.Tech 2nd year Computer Science And Engineering M.N.N.I.T ALLAHABAD -- 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. -- 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] spoj problem
@Akshata, Satyam: I think that might be because the way you are using to
calculate gcd is inefficient.
I got AC.
I used the following technique to calculate gcd:
long long int gcd(long long int a, long long int b){
long long int rem = a%b;
if(rem == 0) return b;
return gcd(b,rem);
}
long long int gcdvar = a[1]-a[0];
for(i=2;in;i++)
{
gcdvar = gcd(a[i]-a[0],gcdvar);
}
Thanks,
Balaji.
On Sat, Mar 12, 2011 at 7:16 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Balaji:
that WA was due to using int in place of long long in loop. But still, this
is giving TLE.
On Sat, Mar 12, 2011 at 7:07 PM, Akshata Sharma akshatasharm...@gmail.com
wrote:
sorry, @satyam: then what is the 'best' solution for this? :)
On Sat, Mar 12, 2011 at 7:06 PM, Akshata Sharma
akshatasharm...@gmail.com wrote:
@Ankur: then what is the 'best' solution for this? :)
@Balaji: i tried implementing but I dont know which case it fails??
getting WA now!!
Here is the code:
#includestdio.h
int main()
{
long n,gcd=1;
scanf(%d,n);
long long a[n],b[n],cnt=0,sum=0;
long long min=9;
scanf(%lld,a[0]);
for(long i=1;in;i++)
{
scanf(%lld,a[i]);
b[i-1]=a[i]-a[0];
if(minb[i-1])
min=b[i-1];
}
for(int k=min;k0;k--)
{
cnt=0;
for(int i=0;in-1;i++)
{
if(b[i]%k==0)
cnt++;
}
if(cnt==n-1)
{
gcd=k;
break;
}
}
sum=((a[n-1]-a[0])/gcd)-n+1;
printf(%lld\n,sum);
return 0;
}
On Sat, Mar 12, 2011 at 2:38 PM, Satyam Kapoor satyamkapoo...@gmail.com
wrote:
this is gud but not the best soln.
--
Satyam Kapoor
B.Tech 2nd year
Computer Science And Engineering
M.N.N.I.T ALLAHABAD
--
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] spoj problem
Yeah, I too am wondering how to implement more efficiently. On Sat, Mar 12, 2011 at 7:36 PM, Satyam Kapoor satyamkapoo...@gmail.comwrote: @balaji:i hve got ac with gcd method but the time is 0.32 sec best soln is 0.03 how is that achievable? -- Satyam Kapoor B.Tech 2nd year Computer Science And Engineering M.N.N.I.T ALLAHABAD -- 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] spoj problem
Try with trees at 1 3 and 5. Gives wrong output: http://ideone.com/KHUdT
And after you fix that if you still get TLE, there is a simpler way to solve
this.
Thanks,
Balaji.
On Sat, Mar 12, 2011 at 12:55 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com
wrote:
CAN ANYONE PLEASE TELL ME WHICH TEST CASE IS WRONG .
PROBLEM:https://www.spoj.pl/problems/STREETR/
#includestdio.h
main()
{
long long int n,i,ans,k,flag,m,a[100100],d;
scanf(%lld,n);
for(i=0;in;i++)
{
scanf(%lld,a[i]);
}
d=a[1]-a[0];
m=1;
while(d0)
{
m=1;
ans=0;
flag=1;
for(i=1;in;i++)
{
if((a[i]-a[0])%d==0)
{
k=(a[i]-a[0])/d+1;
ans=ans+(k-m-1);
m=k;
}
else
{
flag=0;
break;
}
}
if(flag==0||ans==0)
d=d-1;
else
{
//h=0;
break;
}
}
printf(%lld\n,ans);
return 0;
}
--
UTKARSH SRIVATAV
CSE-3
B-TECH 2nd YEAR
MNNIT ALLAHABAD
--
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] Array Question
Here are two methods to do in O(n^2) 1) Insert elements of first array in hash and then for every pair of elements in (Bj, Ck) find if -(Bj + Ck) is in hash 2) Without extra space: sort arrays A and B now for each element in Ck find a pair (Ai, Bj) which sums to -Ck as below let p1 point to first element in A let p2 point to last element in B if p1 + p2 -Ck move p1 one step to right if p1 + p2 -Ck move p2 one step left if ( p1 + p2 == -Ck ) return triplet Thanks, Balaji. On Thu, Feb 17, 2011 at 11:42 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: i have a n^2logn solution sort the third array,.. then for every pair in a and b search for the number which makes the sum zero using binary search but guess a better soln must exist On Thu, Feb 17, 2011 at 11:38 PM, bittu shashank7andr...@gmail.comwrote: We have three arrays A=[a1,a2,...an] B=[b1,b2,...bn] C=[c1,c2,...cn] Write a method which takes these three arrays as input and return true if there is a combination [ai,bj,ck] such that ai+bj+ck = 0. O(n^3) solution is obvious. The questions is can we do better than this? Thanks Regards Shashank Mani -- 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. -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems B.Tech IIIT ALLAHABAD -- 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] Re: SPOJ problem code:MAJOR
@Akshata
I managed to get AC with majority algorithm.
suggestions:
1) You can try to read input and find candidate in same loop
2) Use scanf and printf
Thanks,
Balaji.
On Tue, Feb 15, 2011 at 4:30 PM, jai gupta sayhelloto...@gmail.com wrote:
#includestdio.h
#includestring.h
#includemalloc.h
void work() {
int n,max,maxpos,x,i;
scanf(%d,n);
int *arr=(int*) malloc(sizeof(int)*2005);
memset(arr,0,2005);
max=maxpos=0;
for(i=0;in;i++)
{
scanf(%d,x);
arr[x+1000]++;
if(arr[x+1000]max)
{
max=arr[x+1000];
maxpos=x;
}
}
if(maxn/2)
printf(YES %d\n,maxpos,max);
else
printf(NO\n);
}
int main() {
int t;
scanf(%d,t);
while(t--)
work();
return 0;
}
--
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] Re: first larger element in unsorted array...
Hi,
This can be solved the technique to use stacks to save incomplete problems.
Push first element to stack.
While iterating over the array,
if the element is smaller than stack top, push it to stack along with index.
if the element is larger than stack top, pop till current element
is smaller than stack top and for all the popped indices store the
current element.
time complexity: o(n)
space complexity: o(n)
The same technique is used to solved largest rectangle in a histogram
and largest rectangle with all 1s in a binary matrix.
Thanks,
Balaji.
On Mon, Jan 31, 2011 at 1:25 PM, ritu ritugarg.c...@gmail.com wrote:
for {9,7,8} it gives me {8,8,-1}...not correct
On Jan 31, 11:16 am, abhijith reddy abhijith200...@gmail.com wrote:
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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] NAGARRO CODING QUES............
We do not compare to a value. We compare each pair to current min and if the absolute sum of the current pair is less than the current min, we make the current pair sum the current min. Do checkout this link: http://geeksforgeeks.org/?p=4034 Thanks, Balaji. On Tue, Jan 25, 2011 at 9:35 AM, siddharth srivastava akssps...@gmail.comwrote: Hi On 24 January 2011 12:55, Balaji Ramani rbalaji.psgt...@gmail.com wrote: @Siddharth However if the input range is unknown, it can be solved through an entirely different approach after sorting and then using two pointers moving either side from the positive-negative boundary. O(nlogn) + O(n) = O(nlogn) yes I meant this case only. But to what value would you compare if you want the sum to be closest to zero and lets say that none of the elements sum up to zero. Thanks, Balaji. On Mon, Jan 24, 2011 at 11:03 PM, siddharth srivastava akssps...@gmail.com wrote: If the same question is modified as: Find two numbers whose sum is closest to zero in the given array. On 24 January 2011 16:08, juver++ avpostni...@gmail.com wrote: Its name is meet-in-the-middle technique. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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.comalgogeeks%2bunsubscr...@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] NAGARRO CODING QUES............
Hi,
I just modified the powerset problem to print only if the sum is matched as
below.
http://codepad.org/B72idYnp
I think this algo is order of exponential time on number of elements in the
set.
I would be interested to know if there are more efficient algorithms.
Thanks,
Balaji.
On Mon, Jan 24, 2011 at 3:24 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote:
hello..
Qs:- Given an Array of contain elements range from 1 to 9 find
all possible subsets and print all subsets whose sum is 10,
Assume all elements in the array are distinct.
Exa:- input:---{1,2,6,3,4};
Output:-
{4,6}, {1,6,3}, {1,2,3,4}
input :-{9,8,7,6};
output:-
No
Thanks And Regards
Umesh Kumar
--
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.comalgogeeks%2bunsubscr...@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] NAGARRO CODING QUES............
@Siddharth If the range is 0 to 9 as specified in the first problem statement, it will be just finding the two minimum elements. However if the input range is unknown, it can be solved through an entirely different approach after sorting and then using two pointers moving either side from the positive-negative boundary. O(nlogn) + O(n) = O(nlogn) Thanks, Balaji. On Mon, Jan 24, 2011 at 11:03 PM, siddharth srivastava akssps...@gmail.comwrote: If the same question is modified as: Find two numbers whose sum is closest to zero in the given array. On 24 January 2011 16:08, juver++ avpostni...@gmail.com wrote: Its name is meet-in-the-middle technique. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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.comalgogeeks%2bunsubscr...@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] Largest BST in Binary Tree
I came up with the following O(n) algo involving passing a few extra
parameters by reference. I believe it works.
Traverse the tree. From each node to the parent, return the following
set of values.
1) If BST, size of the current BST or -1 if the tree is not.
2) Minval Maxval of the subtree and maxbstsize seen so far (
probably using references)
So in each node check the following:
If( leftmax node-data node-data rightmin){ // Means it is a BST
{
new size = rightsize+leftsize+1
update size if greater than max
return size
}else{
return -1;
}
Find C++ code here: http://codepad.org/AgJy7BOJ
Thanks,
Balaji.
On Sat, Jan 15, 2011 at 7:02 PM, Decipher ankurseth...@gmail.com wrote:
Find the largest BST in a binary tree ? What's the complexity of your algo
(Amazon Question).
--
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] Building A Special Tree
Sorry, I misunderstood 'at most' in the question. Thanks, Balaji. On Sat, Jan 15, 2011 at 11:27 AM, Decipher ankurseth...@gmail.com wrote: @balaji - In the first tree , 9 has one only child which is not possible for this question. @juver++ - Can you give some algo for this problem -- 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] Building A Special Tree
Two different binary trees can have same set of Leaves/Inner Nodes and same Preorder traversal 5 / \ 3 10 / \ 1 9 \ 7 5 / \ 3 9 / / \ 1 7 10 So, I guess it is not solvable unless we have some more information. Thanks, Balaji. On Fri, Jan 14, 2011 at 10:50 AM, Decipher ankurseth...@gmail.com wrote: A special type of tree is given, where all leaf are marked with L and others are marked with N. every node can have 0 or at most 2 nodes. Trees preorder traversal is given give a algorithm to build tree from this traversal. -- 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.comalgogeeks%2bunsubscr...@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] Building A Special Tree
If I am getting the question right, I believe both the above trees represent this input: 5(N) 3(N) 1(L) 9(N) 7(L) 10(L) 5 / \ 3 10 / \ 1 9 \ 7 5 / \ 3 9 / / \ 1 7 10 Let's get to this very simple example below: 5(N), 9(L) is the input. The tree could be one of the below and hence not unique. 55 / \ 9 9 Did I get the question wrongly ? Thanks, Balaji. On Fri, Jan 14, 2011 at 10:39 PM, juver++ avpostni...@gmail.com wrote: @balaji_ramani That is why there is additional info (L or N). So it is solvable during dfs. -- 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.comalgogeeks%2bunsubscr...@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.
