[algogeeks] Re: Max-Overlapping Intervals
igor way is the optimized way using prefix sum just a small correction with
in life period of (l,r) you have to do v[l]++, v[r+1]--(v is initialized
to zero ) take a prefix sum of v and return the max value containing index
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
ohh..sorry you have to return interval so give the starting index of prefix
sum array to the last index of containing the maximum value of array
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
yeah interval tree and binary indexed tree is a one solution which will
give you answer in log(n) time for each query ,but if i got all the
interval at the beigning of time i can get solution in O(1) time by O(n
) preprocessing take array f initialize with zero,now for each
interval(l,r) do f[l]++ and f[r+1]-- once you are done wi all queries take
prefix sum value of each index will tell you in how many interval it was
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
There are n Intervals. Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 - 1 as 2 lies only in 1 interval [2,3]
For 4 - 3 as 4 lies in 3 intervals
For 11 - 0 as 11 lies in none of the given 4 intervals.
It can be easily done in O(m*n) by traversing n intervals for each number
in the given set of m numbers. How would improve this?
Note: I could not fully recall, but I have seen very similar question in
codechef but could not find the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
typo mistake take prefix sum of f and see each index value...continue
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
There are n Intervals. Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 - 1 as 2 lies only in 1 interval [2,3]
For 4 - 3 as 4 lies in 3 intervals
For 11 - 0 as 11 lies in none of the given 4 intervals.
It can be easily done in O(m*n) by traversing n intervals for each number
in the given set of m numbers. How would improve this?
Note: I could not fully recall, but I have seen very similar question in
codechef but could not find the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: perfect square condition checking....
On Sunday, December 23, 2012 9:07:53 PM UTC+5:30, Anil Sharma wrote: please suggest some efficient solution to check perfect square condition . no matter how much large number is... eg..i/p-8949 o/p-93 there is no specific algorithm for it but yeah you can use binary search for (bisection method )... or use the property that number of divisor of a perfect square is always odd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: DP equation for interval problem
NO its not 2^m ,,, you have to use sorting technique .generally we t do such sorting thing in time interval scheduling(standard greedy problem).in case you didn,t understand let me know ... On Monday, January 28, 2013 1:43:35 PM UTC+5:30, emmy wrote: by match u mean that number of fruits that overlap with i th fruit but are not sliced before time i. which means we have to consider 2^m cases where m is the maximum number of fruits that overlap with ith fruit. And this we have to do for each fruit. On Mon, Jan 28, 2013 at 12:54 AM, Nikhil Karnwal sunny...@gmail.comjavascript: wrote: Actually dp[i] represent the state in which u make a slice at appearing time of i th fruits.and match represent the overlapping fruits with i. so for each i dp[i]=max(dp[i],dp[j]+match); for all j=[0,i] and match =overlapped fruits with i which are not sliced until the cut of j. Hope this will help. Thanks On Thu, Jan 24, 2013 at 10:18 PM, foram lakhani foraml...@gmail.comjavascript: wrote: Thanx for the reply but I didnt get you. What does dp[i] represent ? On Thu, Jan 24, 2013 at 9:50 PM, sunny sharad...@gmail.comjavascript: wrote: take a structure or pair of start time and finish time and then sort the the structure you know the comparator function the for each for each dp[i] select j belongs to (0,i) and then count the overlap value if(j==0) dp[i]=max(dp[i],match); else dp[i]=max(dp[i],dp[j-1]+match); with this recursive relation my code got accepted in .24 sec others approach you mentioned may lead to the TLE On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote: please help me with the following problem: http://www.spoj.com/problems/**JUICE/http://www.spoj.com/problems/JUICE/ bit mask will require very large memory. If I sort the intervals in decreasing order of their start time.. I still cant make it to a dp If I sort the intervals in decreasing order of their finish times I am still not getting a recurrence for dp that is valid If I convert this to an interval graph, I have to find the maximum number of vertices that can be included in some clique of size =3. But this also seems like a brute force approach. Which approach to try?? please help!! -- -- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: DP equation for interval problem
take a structure or pair of start time and finish time and then sort the the structure you know the comparator function the for each for each dp[i] select j belongs to (0,i) and then count the overlap value if(j==0) dp[i]=max(dp[i],match); else dp[i]=max(dp[i],dp[j-1]+match); with this recursive relation my code got accepted in .24 sec others approach you mentioned may lead to the TLE On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote: please help me with the following problem: http://www.spoj.com/problems/JUICE/ bit mask will require very large memory. If I sort the intervals in decreasing order of their start time.. I still cant make it to a dp If I sort the intervals in decreasing order of their finish times I am still not getting a recurrence for dp that is valid If I convert this to an interval graph, I have to find the maximum number of vertices that can be included in some clique of size =3. But this also seems like a brute force approach. Which approach to try?? please help!! --
[algogeeks] Re: array problem
use the concept of segment tree+lazy propagation
On Saturday, August 25, 2012 2:39:54 AM UTC+5:30, wentworth miller wrote:
Hi,
You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It means
that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).
1=N=5 and
t is the number of test cases where 1=t=10
all numbers fit in the 32 bit integer range...
suggest some solution..
here is my solution
but it is giving wrong answer fo some unknown test case...plz suggest me
the test case where i am getting wrong answer
#includestdio.h
#includemath.h
int main()
{
int list[5],i,n,j,sum,k,l;char c;long t;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
for(i=0;in;i++)
{
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);
}
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);
t=2*t;
while(t)
{
sum=0;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);
fflush(stdin);
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d
%d,k,l);
if(c=='Q')
{
for(i=k-1;il-1;i++)
{
for(j=i+1;jl;j++)
{
if(list[i]==list[j])
break;
else if((j==l-1) (list[i]!=list[j]))
{
sum=sum+list[i];
}
}
}
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%d\n,sum+list[l-1]);
}
if(c=='U')
{
list[k-1]=l;
}
t--;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/wLRpyiBiLuoJ.
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] doubt in lca
C itself On Sat, Mar 17, 2012 at 8:39 PM, rahul sharma rahul23111...@gmail.comwrote: in binary tree.. suppose c is parent of dnow if i want to find least common ancesor of c and dwhther it is parent of c or c itself -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 problem
@atul
if its sum of numbers lesser than a[i] in left to i, then still i think it
can be solved in O(nlgn) using Balanced Tree structures
ie: if we use AVL tree, then we just need a little care of how to update
sum stored with rotations
and required ans for ith index must be calculated just after the ith
insertion
and if its sum of numbers lesser than i, then first sort(val, index pair)
the array and find the prefix sum array would do, with some care for
duplicates
On Mon, Mar 12, 2012 at 11:09 PM, atul anand atul.87fri...@gmail.comwrote:
@sunny : it was a reply to different question.
using AVL or RB for the given algo may screw it.
On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
@atul
TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree
as already mentioned in her last post
On Mon, Mar 12, 2012 at 10:44 PM, atul anand atul.87fri...@gmail.comwrote:
@payal:
TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed
is balanced.
so worst would be O(n^2)
On Mon, Mar 12, 2012 at 9:16 PM, payal gupta gpt.pa...@gmail.comwrote:
@atul...
if its the sum of the elements to the left of a[i] which are smaller
the my approach works w/o any flaw
here's the working code for ithttp://ideone.com/CH7VW
if its the sum of all elements lesser than the element a[i] then this
algo is surely wrong
n we then have to proceed by the avl trees or some height balanced tree
n the algo would be of TC-O(nlogn)
btw nyc catch thnx...
Regards,
PAYAL GUPTA
On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor pkjee2...@gmail.comwrote:
1)First map the array numbers into the position in which they would
be, if they are sorted,for example
{30,50,10,60,77,88} --- {2,3,1,4,5,6}
2)Now for each number ,find the cumulative frequency of index ( = the
corresponding number in the map - 1).
3)Output the cumulative frequency and increase the frequency at the
position (=the corresponding number in the map) by the number itself.
Example
{3,5,1,6,7,8} Map of which would be {2,3,1,4,5,6}
Process the numbers now,
1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
0. so output 0
Increase the frequency at index 2 to the number 3.
2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
Increase the frequency at index 3 to the number 5.
3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
position 1 by 1.
Similarly for others.
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: ARICENT PATTERN
this is not the right place to ask such queries On Sun, Feb 26, 2012 at 5:38 PM, vivek kumar kumarvivek1...@gmail.comwrote: hey guys any one have idea about aricent online paper .. plzzz tell me thankss On Sat, Feb 25, 2012 at 8:25 PM, vivek kumar kumarvivek1...@gmail.comwrote: can u provide me some question On Thu, Feb 23, 2012 at 1:59 AM, saurabh tripathi sonu6...@gmail.comwrote: Question in each section varies from 20-25.If u clear this round u have 95% chances because after this round there will b no elimination round. So, all the best. On Wed, Feb 22, 2012 at 10:51 AM, vivek kumar kumarvivek1...@gmail.comwrote: thanks bro ... plz tell me no of question in each section -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Maximize XOR
Given an array of N integers, Find two Numbers with max XOR value. Naive Algorithm is O(N^2), what can be a better approach ? -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 : Any hints[kth smallest contiguous sum] ?
i dont know if a better solution exists but here is one with complexity O(N*logS)... N = no of elements in array S = max sum of a subarray that is sum of all the elements as all are positive algo goes as follows do a binary search in range 0-S, for each such candidate sum find how many sums are smaller than candidate sum there is also need to take care of some cases when there are exactly k-1 sums less than candidate sum, but there is no contigious where sum = candidate sum. On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote: Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/ -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 : Any hints[kth smallest contiguous sum] ?
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k =
3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from the
beginning ? can you explain for that same example... should we check for
all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly k-1
sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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 : Any hints[kth smallest contiguous sum] ?
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.com wrote:
@sunny : before moving to your algorithm , i can see wrong output in your
example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u can
add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find a
index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5}) k
= 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.com
wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly
k-1 sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not add
to the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in
your example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.com
wrote:
we need to find how many sums are less than candidate Sum chosen in one
iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i are
lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say that
i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u
can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to find
a index g such that sum[g - i] candidate sum, and increase the count by
((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5})
k = 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start from
the beginning ? can you explain for that same example... should we check
for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all are
positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find how
many sums are smaller than candidate sum
there is also need to take care of some cases when there are exactly
k-1 sums less than candidate sum, but there is no contigious where sum =
candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
*NO, u r getting it wrong*
*given a value x, we can find how many contiguous sums are lesser than x
using the above mentioned algorithm in O(N)*
*so we are searching a x in range 0-S such that, x has exactly k-1 sums
lesser than x and x is kth*
*
*
*Algorithm: *
*for
*
On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote:
/*
algo goes as follows
*do a binary search in range 0-S*, for each such candidate sum find how
many sums are smaller than candidate sum
*/
do a binary search in range 0-S-- to search what??
acc to the complexity , O(N *log S) it seems that you are searching each
element in given input array from range 0-S
for given input = 1,2,3,4,5
S= 15
please clarify . sorry but i am not getting it ...
On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
Yes, read my first post
On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote:
sum[0-1] = 3 -- (1,2)
sum[0-2] = 6 -- (1,2,3)
sum[1-2] = 5 -- (2,3)
ok...so we can consider 3 , (1,2) as different contiguous.
how did you choose candidate sum for the given input ?? will it not add
to the complexity
On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
@atul there are 8 sums less than 7
sum[0 - 0] = 1
sum[1-1] = 2
sum[2 - 2] = 3
sum[3-3] = 4
sum[4-4] = 5
sum[0-1] = 3
sum[0-2] = 6
sum[1-2] = 5
contiguous sum (1,2) , (2,3) -- these contiguous sum has already been
counted ??? where ?
Read problem statement carefully !!
On Wed, Feb 22, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.comwrote:
@sunny : before moving to your algorithm , i can see wrong output in
your example:-
in you example dere are 8 sums less than 7.
but for given input contiguous sum less than 7 are
1,2,3,4,5 = 4
so output is 4.
correct me if i am wrong...
On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
we need to find how many sums are less than candidate Sum chosen in
one iteration of binary search in range 0-S
To count this, for each i we try to find how many sums ending at i
are lesser than candidate sum !!
lets say for some i-1 sum[0 - i-1] candidate sum then we can say
that i*(i-1)/2 sums are less than candidate sum.
now lets say after adding a[i] again sum[0 - i] candidateSum then u
can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
. sum[i - i] will be lesser than candidate sum
or if adding a[i] causes sum[0 - i] candidateSum then u have to
find a index g such that sum[g - i] candidate sum, and increase the
count
by ((i)-(g) +1).
eg lets say your candidate sum is 7 (for the given
example{1,2,3,4,5}) k = 3 n = 5
initially g = 0
sum = 0;
candidateSum = 7;
count = 0
iteration one:
sum[0 - 0] = 1 7 so count += 0-0+1;
iteration 2
sum[0-1] = 3 7, count += 1-0+1
iteration 3
sum[0-2] = 6 7 count += 2-0+1;
iteration 4
sum[0,3] = 10 7 so now increment g such that sum[g,i] 7
so g = 3count += 3-3+1;
iteration 5
sum[3 - 4] = 9 7
new g = 4 count += 4-4+1
final count = 8, so there are 8 sums less than 7
On Wed, Feb 22, 2012 at 12:16 AM, shady sinv...@gmail.com wrote:
didn't get you, how to check for subsequences which doesn't start
from the beginning ? can you explain for that same example... should we
check for all contiguous subsequences of some particular length?
On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
i dont know if a better solution exists
but here is one with complexity O(N*logS)...
N = no of elements in array
S = max sum of a subarray that is sum of all the elements as all
are positive
algo goes as follows
do a binary search in range 0-S, for each such candidate sum find
how many sums are smaller than candidate sum
there is also need to take care of some cases when there are
exactly k-1 sums less than candidate sum, but there is no contigious
where
sum = candidate sum.
On Tue, Feb 21, 2012 at 11:02 PM, shady sinv...@gmail.com wrote:
Problem link http://www.spoj.pl/ABACUS12/status/ABA12E/
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks]
in Miller Rabin random value a is lesser than n...
i think u r missing it, isn't it ??
On Wed, Jan 18, 2012 at 3:28 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#includeiostream
#includeconio.h
#includemath.h
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int s,d;
for(s=0;1sn;++s); s--;d=(n%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
printf(x is %llu\n,x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k100;k++)
{
printf(%d is %d\n,k,is_prime(k));
}
getch();
}
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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]
That is Okay but for checking a number n to be prime the chosen values of a
should be less than n according to algorithm
On Wed, Jan 18, 2012 at 3:45 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singh singhsourab...@gmail.com wrote:
@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#includeiostream
#includeconio.h
#includemath.h
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int s,d;
for(s=0;1sn;++s); s--;d=(n%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
printf(x is %llu\n,x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k100;k++)
{
printf(%d is %d\n,k,is_prime(k));
}
getch();
}
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] probability of winning with two cards
isn't the answer will be 1/3, without any calculations :) On Thu, Jan 19, 2012 at 7:10 AM, Sundi sundi...@gmail.com wrote: there are 52 cards.. there are 3 players a1,a2,a3 each player is given 2 cards each one of A=2...J=11,Q=12,K=13..a user wins if his sum of cards is greater then the other two players sum. find the probability of a1 being the winner? -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: number of form m^n
considering number to be a 32 number(also applicable in the same way to 64 bit) one possibility is let x be the number find log10x for 32 bit numbers max value of n is 64 so for n = 1 to 64 find p = logx10/n take antilog and take nearest integer as m m = 10^p; again find m^n if it is equal to x return m,n seems to be okay have to conform the correctness :) On Tue, Dec 27, 2011 at 6:41 PM, SAMMM somnath.nit...@gmail.com wrote: I know tht it need GCD(a,b,) where N = p^a q^b... I wrote it previously ... it's just tht my lates reply is not in sequence . I hav added tht later .. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Why moderated?
this is not suddenly, this is happening from the last few months, you might not have noticed. this was done because of a lot of unrelated topics and interview queries. one better thing that can be done is to allow some users for direct posting :) On Tue, Dec 27, 2011 at 3:34 PM, Lucifer sourabhd2...@gmail.com wrote: Hey Guys, Why suddenly all the posts are being moderated.. I think by doing so we will fall out of sync on who is posting what.. Do you guys agree ? I think the posts should be updated instantly.. What do u think? -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Suggest Algo for this Question
oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.comwrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.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
Re: [algogeeks] Re: Suggest Algo for this Question
i am Considering given heap as min heap Sol - because heap has property that root will has lower value than all the elements in its left sub tree and right sub tree so in main we will call a function passing root and value k and x if at any time root is greater than x and k 0 that means rest of the elements are greater than x so kth is also greater than x else make recursive calls for both of its child as soon as k hits zero in any recursive call we know that there are k elements less than x. i think in worst case 2k comparisons will be there hence O(k) On Wed, Dec 14, 2011 at 12:24 PM, atul anand atul.87fri...@gmail.comwrote: yup rite...it should be O(k log n ) not O(n log n). On Wed, Dec 14, 2011 at 11:44 AM, Dave dave_and_da...@juno.com wrote: @Atul: The initial heap is given. You have to maintain the heap property as k elements are removed, which is O(k log n). This does not satisfy the original request for an algorithm that is O(k) in the worst-case, independent of the size of the heap. Dave On Dec 13, 10:31 pm, atul anand atul.87fri...@gmail.com wrote: @gaurav : you need to first build heap and then maintain heap property ever time you remove element.so this would take O(n logn ). On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote: Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Suggest Algo for this Question
@shashank nope only 2k comparisions k numbers which are greater than x and k which are less than x dont think in terms of root and child On Thu, Dec 15, 2011 at 12:57 PM, WgpShashank shashank7andr...@gmail.comwrote: more clarification , why number of comparisons are 3k , because we are looking for only those nodes which are less then x and each nodea can max 2 childs , so tottal 3k comparisons . so it will O(3K) . Thanks Shashank CSE , BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OALJEqbuE_MJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] MYSIS AND DRISHTI-SOFT
@aayush Lots of member are here but that doesn't mean that you should start posting the things which are strictly banned on this group. I hope you will take care next time while posting anything in this group. On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote: On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.comwrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] MYSIS AND DRISHTI-SOFT
http://groups.google.com/group/interview-street On Tue, Dec 13, 2011 at 10:19 PM, tech coder techcoderonw...@gmail.comwrote: which other group u people are talking about, i would like to join that group. On Tue, Dec 13, 2011 at 9:21 PM, sunny agrawal sunny816.i...@gmail.comwrote: @aayush Lots of member are here but that doesn't mean that you should start posting the things which are strictly banned on this group. I hope you will take care next time while posting anything in this group. On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote: On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.comwrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Fill tool
http://www.gild.com/challenges/details/295 No of connected components, use BFS/DFS On Sun, Dec 4, 2011 at 9:12 PM, rajesh ko ko.rajes...@gmail.com wrote: We have given a black and white image and a fill tool that turn an area of black pixel into white pixels. Fill tool works like a 8-way floodfill tool.So it will turn each black pixel to a white pixel untill there isn't a blackpixel that can be reached from the previous pixel. (8 ways - north,east,west,south and four corners). Q : Given a black and white image of dimension x*y , Determine how many time we have to apply fill tool to turn the whole image into a white one. For simplicity consider an image is a matrix of size x*y. in example 1- white pixel and 0- black pixel. eg: i/p: 3 5 10111 10100 00111 o/p: 2 -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Modular Arithmetic and Number Theory
Given a, n, P find the value of a^(nth Fibonacci number) % P where a and P are *not* Co-prime -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Finding the repeated element
i also doubt about the time and space complexity of the problem, i has been asked a number of times with these constraints but never been answered the required, as far as i remember the best solution to this problem that has been discussed so far is using hashing and that too theoretically having TC and SC of O(n). On Thu, Nov 24, 2011 at 7:12 PM, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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
one solution is use BFS
On Mon, Nov 14, 2011 at 8:52 PM, Anshul AGARWAL
anshul.agarwa...@gmail.com wrote:
i m try to increase current floor c by push up button until it equal or
greater than g and increase co-responding push p.when my current
floor is greater than g.i push down button once and increase p by 1.
repeat this loop until i get c==g.
Anshul Agarwal
Nit Allahabad
Computer Science
On Mon, Nov 14, 2011 at 9:50 AM, shady sinv...@gmail.com wrote:
what;s your algorithm ?
On Mon, Nov 14, 2011 at 7:57 PM, Anshul AGARWAL
anshul.agarwa...@gmail.com wrote:
problem is http://www.spoj.pl/problems/ELEVTRBL/
and my solution is give wrong answer on spoj . Plz help me to find in
which case my solution give wrong answer.
#includeiostream
#includestdio.h
using namespace std;
int main()
{
long long int f,s,u,d,g,c,p;
scanf(%lld%lld%lld%lld%lld,f,s,g,u,d);
p=0;
if(s==g)
printf(0\n);
if(sgu==0d!=0)
{
int temp=s-g;
if((temp/d)*d==temp)
{
p=temp/d;
printf(%lld\n,p);
}
else
printf(use the stairs\n);
}
else if(sg)
{
int temp =s;
s=g;
g=temp;
// cout2endl;
}
//cout1endl;
c=s;
if(sg)
{ while(1)
{
int temp=g-c;
int q;
if(u==0)
{
if(c==g)
{
printf(0\n);
break;
}
else
{
printf(use the stairs\n);
break;
}
}
if(temp/u==(temp/u)*u)
{
q=temp/u;
}
else
q=temp/u+1;
if((c+q*u)=f)
{ // cout1endl;
p=p+q;
c=(q)*u+c;
//coutcendl;
}
else
{//cout2endl;
p=p+temp/u;
c=(temp/u)*u+c;
}
if(c==g)
{
// cout3endl;
printf(%lld,p);
break;
}
if(u==d||d==0||((u%d==0)d!=0)||(d%u==0u!=0))
{
printf(use the stairs\n);
break;}
if(c-d=0)
{ // cout4endl;
c=c-d;
p+=1;
// coutcendl;
}
else
{
// cout5endl;
printf(use the stairs\n);
break;
}
}
}
}
Anshul Agarwal
Nit Allahabad
Computer Science
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: Facebook Campus Test Question
i/p o/p files are attached in the post, see carefully :-o On Fri, Nov 4, 2011 at 6:23 PM, Dumanshu duman...@gmail.com wrote: plz post a samle input output.. On Nov 4, 10:24 am, sunny agrawal sunny816.i...@gmail.com wrote: What can be a better solution than a Brute Force O(N^2* No of iteration) -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee fb1_input.txt 1KViewDownload facebook.jpg 119KViewDownload fb1_output.txt 1KViewDownload -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Facebook Campus Test Question
No,O(N^2) because all the flips happens simultaneously, it can be reduce to O(2N) if each tile is represented using a single bit On Fri, Nov 4, 2011 at 11:12 PM, Dumanshu duman...@gmail.com wrote: is ur brute force O(1) for space? On Nov 4, 10:24 am, sunny agrawal sunny816.i...@gmail.com wrote: What can be a better solution than a Brute Force O(N^2* No of iteration) -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee fb1_input.txt 1KViewDownload facebook.jpg 119KViewDownload fb1_output.txt 1KViewDownload -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 : CODECHEF question
This is a challenge problem and you don't need to find a best solution for each case, optimal solutions are acceptable if they satisfy the problem constraints for this problem the constraint is cuts should be made so that both are able to eat equal no of each available ingredient Examples: Lets take the last testcase 8 500 400 2 400 500 500 2 500 in this testcase as you can see if cuts are made like 500 400 2 | 400 | 500 | 500 2 500 Jack | Jill | Jack|Jill so using only 3 cuts we can divide this so that both get same and equal no of each type of available ingredients Scoring for this problem is done depending upon how many cuts your program outputs relative to others On Wed, Nov 2, 2011 at 6:17 PM, shady sinv...@gmail.com wrote: Hi, Can anyone what is being done here ? This is a question http://www.codechef.com/JAN11/problems/SPLIT/ from Codechef. I have read the editorials, but that didn't help. http://www.codechef.com/download/Solutions/2011/January/Setter/Split.cpp -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 : CODECHEF question
problem setters solution is just a greedy approach as ingredients are represented using integer values ranging less than 500 so he is making a hash map of ingredients which store the frequency of the ingredient, whenever the count for some ingredient goes odd, he makes a cut On Wed, Nov 2, 2011 at 7:25 PM, shady sinv...@gmail.com wrote: actually i wanted to know what approach the problem setter is using, since this problem is NP hard so optimal solution is not always possible. On Wed, Nov 2, 2011 at 7:20 PM, sunny agrawal sunny816.i...@gmail.com wrote: This is a challenge problem and you don't need to find a best solution for each case, optimal solutions are acceptable if they satisfy the problem constraints for this problem the constraint is cuts should be made so that both are able to eat equal no of each available ingredient Examples: Lets take the last testcase 8 500 400 2 400 500 500 2 500 in this testcase as you can see if cuts are made like 500 400 2 | 400 | 500 | 500 2 500 Jack | Jill | Jack| Jill so using only 3 cuts we can divide this so that both get same and equal no of each type of available ingredients Scoring for this problem is done depending upon how many cuts your program outputs relative to others On Wed, Nov 2, 2011 at 6:17 PM, shady sinv...@gmail.com wrote: Hi, Can anyone what is being done here ? This is a question http://www.codechef.com/JAN11/problems/SPLIT/ from Codechef. I have read the editorials, but that didn't help. http://www.codechef.com/download/Solutions/2011/January/Setter/Split.cpp -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Shuffling Arrays
O(n) is possible using in-shuffle but doing it in-place was the problem in case of in-shuffle we need to know which of the elements have been shuffle so we need O(n) bits of extra space; O(nlgn) is possible using a quick sort like divide and conquer algorithm.i read it somewhere and will post it if i am able to find it :) On Wed, Nov 2, 2011 at 7:11 PM, shady sinv...@gmail.com wrote: a1 a2 a3 a4 b1 b2 b3 b4 given these two arrays convert them to a1 b1 a2 b2 a3 b3 a4 b4 i can do this in O(1) space and O(n^2)time is there any O(n) solution for this problem ? I searched in archives, but there people mention about in-shuffle, but how to implement it in O(n) is not clear. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Unique partition
@Mohit
that will also not work
example: {1,1,1,2,2,2,3,3,3}
i think all the methods that try to fill the matrix(considering k sets as k
rows) either horizontally or vertically will fail
we need to fill these both horizontally and vertically at the same time
depending upon the frequency of elements.
On Mon, Oct 31, 2011 at 6:16 PM, mohit verma mohit89m...@gmail.com wrote:
Hi SAMM,
The above code is not clear enough to understand . Sorry for that.
My idea was , like for above example : map will contain frequency of all
distinct elements.
so freq[1] = 6
freq[3]= 1
freq[5]=1
freq[6]=1
Now for n=9 and k=3
P1={1,3,5};
and now after this partition frequency of each element gets reduced by
1.Now you can eliminate elements having 0 frequency or just skip them.
In second run
P2={1,6,1}
and P3={1,1,1}.
On Mon, Oct 31, 2011 at 4:20 AM, SAMM somnath.nit...@gmail.com wrote:
Ur algo will not work for this case :-
1 1 1 1 1 1 3 5 6 For the array .. And for K=3
Ur algo will give (1 1 1) (1 1 1 ) (3 5 6)
On 10/30/11, mohit verma mohit89m...@gmail.com wrote:
sort the array : O(nlogn)
keep an array/map containing frequency of each element in sorted array :
O(n)
v[n/k][k] - 2-D array of ints containing final partitions.
for i=1 to n/k
{
int count=0;
for(j=0;jn count k;j++)
{ if( freq(a[i])==0) continue; //say array is used
v[i][count]=a[i];
freq(a[i])--; //just an idea , not actual implementation
count++;
}
}
you can improve internal for loop by using map : if freq[a[i]] becomes
0
delete the node from array.
On Sun, Oct 30, 2011 at 10:35 PM, SAMM somnath.nit...@gmail.com
wrote:
No there is no such condition ...just hav to make sure all the
partitions are unique .
The partitions can hav some elements ( K) in common but not the
entire elements in a partition (Should be UNIQUE) .
On 10/30/11, sunny agrawal sunny816.i...@gmail.com wrote:
Is there any condition like all sets should have same no. Of elements
On 10/30/11, SAMMM somnath.nit...@gmail.com wrote:
But how does it ensure tht the elements been removed wouldnot give
the same set again
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Somnath Singh
--
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.
--
Mohit
--
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.
--
Somnath Singh
--
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.
--
Mohit
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Unique partition
Is there any condition like all sets should have same no. Of elements On 10/30/11, SAMMM somnath.nit...@gmail.com wrote: But how does it ensure tht the elements been removed wouldnot give the same set again -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Search an element in an Infinite array
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] FACEBOOK ONLINE CODING ROUND
yea i know 1st Approach is much better and is Only O(N^2) for precomputing all the values for nck and then O(k) for finding no of bits set in The Kth number and another loop of O(k) to find the required number i posted 2nd approach in the context to vandana's tree approach of sorting 2^N numbers, rather simply sort the numbers in the array... and this approach is O(N*2^N) On 10/21/11, sravanreddy001 sravanreddy...@gmail.com wrote: @Sunny.. why do we need an O(2^N) complexity? for a value of N=40-50, the solution is not useful.. but, your 1st approach is lot better and i have got it too.. 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1-k (n C i)) 2. again, keep substracting (k-i) for i= 0-k-1 so.. O(k) here and recursively performing step 2. (worst case complexity is O(T)) where T = nCk O(N) + O(T) == O(T) as it dominates the given number. unless it doesn't fall in the range.. or equivalently -- max( O(T), O(N) ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] FACEBOOK ONLINE CODING ROUND
although input is small so a brute force will also do
but some optimization can be like
1. first we can find that how many bits will be set in Kth Codewords using
the following method
no of codewords with N bits set = 1
no of codewords with N-1 bits set = NC1
no of codewords with N-2 bits set = NC2
.
.
.
no of codewords with 1 bits set = NC1
no of codewords with 0 bits set = 1
using these precomputed counts we can get index of the element in the all
numbers having k bits set
so problem will reduce to find the ith element with j bits set
first element of the sequence will be (N-j) 0's followed by j ones then we
can use i-1 calls NextHigherNumberWithSameBitsSet function to get the
required number
again there is one more optimization possible rather than calling function
i-1 times, search archives for the implementation
On Wed, Oct 19, 2011 at 9:03 PM, aritra kundu aritra2123...@gmail.comwrote:
*Question 1 / 1*
Given an integer *N*, there are *2^N* binary codewords of length N. All of
them are taken and sorted to create a sequence: Sort by the number of 1-bits
in the codeword bit-string. If there is a tie, break tie so that the smaller
number comes first in the output sequence
*Testcases format:*
You would be given 2 integers *N* (=10) and *K* (1 = K = 2^N)
Output the codeword with index K into this sequence
The input is from stdin and output to stdout
*Sample Testcases:*
*Input #00:*
3 5
*Output #00:*
011
*Explanation:*
For N = 3, the sequence consists of {000,001,010,100,011,101,110,
111}. The 5th indexed number would be 011
*Input #01:*
7 127
*Output #01:*
110
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] FACEBOOK ONLINE CODING ROUND
No need of creating a tree
simply take an array of size 2^N in which all a[i] initialized to i
now sort the array first depending upon the set bits in the a[i] if set bits
are equal then use value
this function call to sort function of algorithms will do the required
bool cmp(int x, int y){
int count1 = __builtin_popcount(x);
int count2 = __builtin_popcount(y);
if(count1 count2) return true;
if(count1 count2) return false;
return x y;
}
call in main
sort(a,a+(1n), cmp);
On Wed, Oct 19, 2011 at 10:46 PM, Vandana Bachani vandana@gmail.comwrote:
Hi,
logic:
We can work on this problem from the way we construct the sequence.
First we generate a binary tree such that each leafnode corresponds to one
of the 2^N nodes. We start we an empty root, creating 0, 1 nodes assigning
one bit at a time upto N levels (there would be 2^N - leafnodes) but while
doing that we can assign weights and values to each node as we construct the
tree. (In a breadth first fashion). node.weight = node.parent.weight + 0/1
(based on whether it lies on the 0th edge (left edge) of the parent or the
1th edge (right edge) of the parent, we can say 0 ad 1 are respective edge
weights) and node.value = node.parent.value*2 + 0/1.
We will add the leaf nodes to an array(sequence) as they get created when
we reach nth level in the tree. Sort the array of nodes by weight and by
value in case of tie.
-Vandana
On Wed, Oct 19, 2011 at 10:33 AM, aritra kundu aritra2123...@gmail.comwrote:
*Question 1 / 1*
Given an integer *N*, there are *2^N* binary codewords of length N. All
of them are taken and sorted to create a sequence: Sort by the number of
1-bits in the codeword bit-string. If there is a tie, break tie so that the
smaller number comes first in the output sequence
*Testcases format:*
You would be given 2 integers *N* (=10) and *K* (1 = K = 2^N)
Output the codeword with index K into this sequence
The input is from stdin and output to stdout
*Sample Testcases:*
*Input #00:*
3 5
*Output #00:*
011
*Explanation:*
For N = 3, the sequence consists of {000,001,010,100,011,101,110,
111}. The 5th indexed number would be 011
*Input #01:*
7 127
*Output #01:*
110
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] FACEBOOK ONLINE CODING ROUND
yes u r wrong
11
111 = 110 but sequence will be
11
101
110
On Thu, Oct 20, 2011 at 12:18 AM, tin a.gu...@tin.it wrote:
Can you just generate them sorted?
1 is the minimum
1 1 is the next in line
1 2 is the next one
1 N
11
11 1
and so on
Am i wrong?
Il 19/10/2011 19:33, Vandana Bachani ha scritto:
Completing it... Got sent before I completed
On Wed, Oct 19, 2011 at 12:31 PM, Vandana Bachani
vandana@gmail.comwrote:
Better logic:
create a list array of lists 'arr' (like a hash table with lists). Array
size is N represents 1 to N bits and lists that will increase as we add more
elements to it. a.
for(i = 1; i = 2^N; i++)
{
c = count no. of 1s. in i
add i to list arr[c-1].
}
for (i = 0; i N; i++)
{
print list arr[i]
}
On Wed, Oct 19, 2011 at 12:16 PM, Vandana Bachani
vandana@gmail.comwrote:
Hi,
logic:
We can work on this problem from the way we construct the sequence.
First we generate a binary tree such that each leafnode corresponds to
one of the 2^N nodes. We start we an empty root, creating 0, 1 nodes
assigning one bit at a time upto N levels (there would be 2^N - leafnodes)
but while doing that we can assign weights and values to each node as we
construct the tree. (In a breadth first fashion). node.weight =
node.parent.weight + 0/1 (based on whether it lies on the 0th edge (left
edge) of the parent or the 1th edge (right edge) of the parent, we can say 0
ad 1 are respective edge weights) and node.value = node.parent.value*2 +
0/1.
We will add the leaf nodes to an array(sequence) as they get created when
we reach nth level in the tree. Sort the array of nodes by weight and by
value in case of tie.
-Vandana
On Wed, Oct 19, 2011 at 10:33 AM, aritra kundu
aritra2123...@gmail.comwrote:
*Question 1 / 1*
Given an integer *N*, there are *2^N* binary codewords of length N. All
of them are taken and sorted to create a sequence: Sort by the number of
1-bits in the codeword bit-string. If there is a tie, break tie so that the
smaller number comes first in the output sequence
*Testcases format:*
You would be given 2 integers *N* (=10) and *K* (1 = K = 2^N)
Output the codeword with index K into this sequence
The input is from stdin and output to stdout
*Sample Testcases:*
*Input #00:*
3 5
*Output #00:*
011
*Explanation:*
For N = 3, the sequence consists of {000,001,010,100,011,101,110,
111}. The 5th indexed number would be 011
*Input #01:*
7 127
*Output #01:*
110
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Reconstruct BST from preorder traversal
@sravan yes you are given the sequence of elements in the order in which they are traversed in the given traversal (in/pre/post) a BST can be constructed from its post or pre order only but can not be constructed from only inorder in case of inorder we also need one more traversal -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
if(you are a member already) No need to post anything, just ignore the post :) On Mon, Oct 17, 2011 at 5:38 PM, sravanreddy001 sravanreddy...@gmail.comwrote: Wee are already members.. What is expected from us.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/vMtV3ewVYSgJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Find THE NUMBERS URGENT PLZZZZZ HELP...........
This Question is from ACM-ICPC 2011 Amritapuri online round which ends today at 1pm so no answers to this post till 1 pm On Sun, Oct 16, 2011 at 11:12 AM, Pradex pradam.prad...@gmail.com wrote: Given two number A and B, count all the number lies between them including both which have no more than two digit in common 1 = A = B = 10^18 eg. : 100 120 output : 20 excluding 111 please help very important ?? -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Counting Diagonals in a Polygon
CSI : Computer Science Integrated (5yr) CSE is 4 year On Sat, Oct 15, 2011 at 1:59 PM, hary rathor harry.rat...@gmail.com wrote: sunny : are you in 5th year . i have heard that b-tech is 4 year degree?. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Inplace Array Convertion
i have already mentioned the source it is famous shuffling algorithm. u can seach some papers on In-Shuffle and Out-Shuffle the original question in the shuffling is like how many times we need to shuffle the cards after which they will return back to initial sequence. On Sat, Oct 15, 2011 at 5:35 PM, Ankur Garg ankurga...@gmail.com wrote: @Sunny ..Superb Algo ..but can you share some link where we can read abt it :)..especially where the info abt the equation u used is given Thanks in Advance On Sat, Oct 15, 2011 at 12:37 PM, Kunal Patil kp101...@gmail.com wrote: @Sunny: Thanks for the info !! That's gr8.. your logic also seems to be working perfectly fine.. On Sat, Oct 15, 2011 at 12:16 PM, shady sinv...@gmail.com wrote: u can always post the code.,... but before posting code, you must state your algorithm else code becomes useless for other users On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain anika.jai...@gmail.comwrote: i have the code solution to this.. if m allowed to post it here then i can i post it. m i allowed to post code here? On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav gauravyadav1...@gmail.com wrote: @shiva...keep swapping the underline elements a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 -- 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. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Inplace Array Convertion
In/Out Shuffle are two shuffling algorithms used for shuffling cards consider a pack of cards (so N = 52) and let cards are numbered from 1, 52 *In Shuffle *: cards are divided into 2 piles (k = 2) (1,2,3.26) (27,28,...52) afer one shuffle operation cards will be like (27,1)(28,2) ..(52,26) and it can be found that the card at position i(0 indexed) has moved to its new position given by formula *i - 2*i %(N+1) N = 52 *for k piles answer will be simply *k*i % (N+1) N = 52* *Out Shuffle *: cards are divided into 2 piles (k = 2) (1,2,3.26) (27,28,...52) afer one shuffle operation cards will be like (1, 27)(2,28) ..(26,52) and it can be found that the card at position i(0 indexed) has moved to its new position given by formula *i - 2*i %(N-1) N = 52 *for k piles answer will be simply *k*i % (N-1) N = 52 *now relating this to the Question in this thread k = 3 N = total no of elements in the array shuffle is Out shuffle now for writing program i think it can be done in O(2*n) ...will try to code soon :) On Sun, Oct 16, 2011 at 3:16 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Anika, Your algorithm appears to take O(n^2) time and also O(n) space in recursion stack space, storing the 3 elements in recursion level. The direct shifting of elements to the right will take O(n2) time and O(1) space. Please comment if my assumptions are incorrect. Can anyone provide weblink for IN?OUT shuffle card shuffling prob related to this scenario. and Memory efficient rearragnement of array elements. Thanks, sravanreddy001 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/RdrlNoIGpBEJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Counting Diagonals in a Polygon
Are you talking about 7th application th wiki of catalan numbers?? i think here case is differentregions are not necessarily triangles.. ??? On Sun, Oct 16, 2011 at 3:43 AM, sravanreddy001 sravanreddy...@gmail.comwrote: This is calalan Number. where n = k+1 very interesting and complex probs... http://en.wikipedia.org/wiki/Catalan_number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OQ_qMqpAP0YJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Inplace Array Convertion
Its Out Shuffle not In shuffle, although both are similar and you can read both On Fri, Oct 14, 2011 at 8:26 PM, sunny agrawal sunny816.i...@gmail.comwrote: this problem is like Card shuffling problem(search for In-shuffle) i think solution is if indexing is zero based each i will go to - k*i % (N-1) k = 3 and N = 3*n -1 n = no of cards in one pile Or No of a's On Fri, Oct 14, 2011 at 7:52 PM, shiva@Algo shiv.jays...@gmail.comwrote: @Gaurav how will u do for a1a2a3a4a5b1b2b3b4b5c1c2c3c4c5 On Fri, Oct 14, 2011 at 6:49 AM, gaurav yadav gauravyadav1...@gmail.comwrote: consider following example... suppose initailly we have a1a2a3b1b2b3c1c2c3 then do the following- a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with a2 , so in this case swap(a2,b1) ) a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) a1b1c1 a2b2b3 a3c2c3swap(b3,c2) a1b1c1 a2b2c2 a3b2c3 this in inplace (plz correct if im wrong) -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Inplace Array Convertion
this problem is like Card shuffling problem(search for In-shuffle) i think solution is if indexing is zero based each i will go to - k*i % (N-1) k = 3 and N = 3*n -1 n = no of cards in one pile Or No of a's On Fri, Oct 14, 2011 at 7:52 PM, shiva@Algo shiv.jays...@gmail.com wrote: @Gaurav how will u do for a1a2a3a4a5b1b2b3b4b5c1c2c3c4c5 On Fri, Oct 14, 2011 at 6:49 AM, gaurav yadav gauravyadav1...@gmail.comwrote: consider following example... suppose initailly we have a1a2a3b1b2b3c1c2c3 then do the following- a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with a2 , so in this case swap(a2,b1) ) a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) a1b1c1 a2b2b3 a3c2c3swap(b3,c2) a1b1c1 a2b2c2 a3b2c3 this in inplace (plz correct if im wrong) -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Counting Diagonals in a Polygon
Given a n vertex polygon, find in how many ways k non intersecting diagonals can be drawn ? or in How many ways it can be divided into k+1 regions such that no 2 diagonals intersect ? Limits:1 = k = N = 10^9 -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Algo for Search in a 2D Matrix
@Anshu pushing adjacent element will cause duplicate entries in the heap try the following example: 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 so we also need to maintain a data structure that can efficiently tell that which cell has been pushed into the heap already. On Thu, Oct 13, 2011 at 11:35 AM, anshu mishra anshumishra6...@gmail.comwrote: push the two adjacent element that is one right and below -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: Algo for Search in a 2D Matrix
Nopes
Still it does not ensure that duplicates will not be there in the priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other than heap,
which stores that which (i+1,j) are already there in the heap map can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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: Algo for Search in a 2D Matrix
i dont think k*k submatrix approach works at all what if k =n size of submatrix will be n*n, which is matrix itself heap seems to be a good approach with a coloring scheme that helps in avoiding duplicates in heap ?? On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.com wrote: @Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursively to find the element Any suggestions ? On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote: id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Stone Game
your solution seems to be the right one... testcases may be faulty
try submitting here http://www.codechef.com/problems/RESN04/ both the
codes
On Thu, Oct 13, 2011 at 5:44 AM, Hatta tmd...@gmail.com wrote:
being accepted doesn't imply in being correct
maybe I'm wrong but given this Test Case I think BOB wins:
3
1 3 2
didn't he (bob!)?
On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares wladimir...@gmail.com
wrote:
In the problem Stone Game , I did the following algorithm that was
accepted
by spoj:
#includestdio.h
int main(){
int n,t,i,j,cont;
scanf(%d,t);
while(t--){
scanf(%d,n);
cont=0;
for(i=1;i=n;i++)
{
scanf(%d,j);
if(j=i){
cont+=j/i;
}
}
if(cont%2==0)
printf(BOB\n);
else
printf(ALICE\n);
}
return 0;
}
A friend of mine made the following code, which was also accepted by
spoj:
#include stdio.h
#include iostream
#include stack
#include queue
#include algorithm
#include iostream
using namespace std;
int main(){
int n;
cin n;
while(n--)
cout ALICE endl;
return 0;
}
I could not prove because Alice always wins. Does anyone know how to
prove
this fact?
Wladimir Araujo Tavares
Federal University of Ceará
Homepage | Maratona |
--
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.
--
Hatta
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] remove duplicate words from a string
1. how we can store the word each seperated by space into array if we are considering binary tree??? Ans: Each Node will Have an array of Some Const Size limited by Max Word length 2. how we can measure which is smaller than other according to property?? Ans Obviously strcmp(str1, str2) - standard library function / or u can implement yours 3. if we store each word into hash table then how we can get those words stored at different places in hash table??? Ans: u have to define some function that takes string as input generates a key. and then use that key for hashing and for different keys your function should be good enough. 4. how we know about the indexes where we have store the word because in the end we have to combine all the wordinto string. Ans: you can keep an extra array to store that for each word -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Fwd: why we can not swap values using macro?
Macros can Swap Pointers. and That is what the above code is doing.
On Mon, Oct 10, 2011 at 5:52 PM, rahul sharma rahul23111...@gmail.comwrote:
macros i thnik cant swap pointers..i have doubt for same it is test ur c
skil question
On Sun, Oct 9, 2011 at 10:08 PM, sunny agrawal sunny816.i...@gmail.comwrote:
because you have not made any call to swap values of x and y
I Don't know what you are trying to do here
if you want to swap values why are you not calling macro swap(x,y,int)
you are making a macro call to swap pointers and you can check that
pointer will get swapped.
On Sun, Oct 9, 2011 at 9:20 PM, Rajesh Kumar testalgori...@gmail.comwrote:
-- Forwarded message --
From: Rajesh Kumar testalgori...@gmail.com
Date: Sun, Oct 9, 2011 at 2:58 PM
Subject: why we can not swap values using macro?
To: algogeeks@googlegroups.com
why this code doesn't swap values of x and y?
#includestdio.h
#define swap(a,b,c) c t;t=a,a=b,b=t;
main()
{
float x=10,y=20;
float *p,*q;
p=x,q=y;
swap(p,q,float *);
printf(%d %d\n,x,y);
}
--
Regards
Rajesh Kumar
--
Regards
Rajesh 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Give Algo to do this in O(n)
Counting Sort is really a Bad option for this Problem as range is not given yes range can be find in single traversal but think if largest element is 10^9 and size of the array is just about 10^3 Counting Sort = O(10^9) Simple Sorting = O(10^4) Counting sort will perform bad in this case both in terms of Space Requirements and Time On Mon, Oct 10, 2011 at 11:25 PM, snehi jain snehijai...@gmail.com wrote: ankur : i wont say its the best way, but it can be used in one traversal the range can be determined and then count sort can be applied. On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg ankurga...@gmail.com wrote: @Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 sravanreddy...@gmail.com wrote: Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] remove duplicate words from a string
Trie will take too much space.. Balanced Binary tree can be Better ...?? On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg ankurga...@gmail.com wrote: I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] remove duplicate words from a string
@Ankur in Trie at each Node there will be 26 Pointers Stored, and Most of them would be NULL, thats why i think it will waste space, in Balanced Binary Tree i was thinking of storing the Complete Words at a Node. But now i think this is Better - Ternary Search Trieshttp://en.wikipedia.org/wiki/Ternary_search_tries -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] what is the use of fflush ?
these are some lines form fflush man pages
For output streams, fflush() forces a write of all user-space buffered data
for the given output or update stream via the stream's underlying write
function. *For input streams, fflush() discards any buffered data that has
been fetched from the underlying file, but has not been by the application.*
*
The standards do not specify the behavior for input streams.* Most other
implementations behave the same as Linux.
On Sun, Oct 9, 2011 at 7:17 PM, Sanjay Rajpal srn...@gmail.com wrote:
Sorry for previous email, did not read the question properly.
Sanju
:)
On Sun, Oct 9, 2011 at 7:12 PM, Sanjay Rajpal srn...@gmail.com wrote:
After scanning the variable a, you will give a whitespace
character(space,tab or newline), which will also get stored into stdin file.
So next statement will scan this whitespace character.
fflush(stdin) flushes(clears) the contents of stdin file, so this time
scanf will not get whitespace character, instead it will get the character
entered by user.
or in second scanf statement, change it as scanf( %c,b), notice the
space before %c.
Correct me if m wrong :)
Sanju
:)
On Sun, Oct 9, 2011 at 6:55 PM, rajul jain rajuljain...@gmail.comwrote:
just take input a and b in one statement like this scanf(%d %d ,a
,b);
On Sun, Oct 9, 2011 at 4:50 PM, Saravanan Selvamani
saravananselvam...@gmail.com wrote:
Hi,
In the following programming when i gave character input rather
than integer , the following scanf statement is not working . so i
introduce
the fflush(stdin) before the last scanf statement.
But i get the same error as i before .
#includestdio.h
int main()
{
int a,b;
scanf(%d,a);
fflush(stdin);
scanf(%d,b);
printf(%d,b); //prints some
garbage value.
return 0;
}
so then what is the use of the fflush(stdin) and how to correct the
above error? Thanks in advance.
Regards
P.S.Saravanan.
--
why so serious?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Fwd: why we can not swap values using macro?
because you have not made any call to swap values of x and y
I Don't know what you are trying to do here
if you want to swap values why are you not calling macro swap(x,y,int)
you are making a macro call to swap pointers and you can check that pointer
will get swapped.
On Sun, Oct 9, 2011 at 9:20 PM, Rajesh Kumar testalgori...@gmail.comwrote:
-- Forwarded message --
From: Rajesh Kumar testalgori...@gmail.com
Date: Sun, Oct 9, 2011 at 2:58 PM
Subject: why we can not swap values using macro?
To: algogeeks@googlegroups.com
why this code doesn't swap values of x and y?
#includestdio.h
#define swap(a,b,c) c t;t=a,a=b,b=t;
main()
{
float x=10,y=20;
float *p,*q;
p=x,q=y;
swap(p,q,float *);
printf(%d %d\n,x,y);
}
--
Regards
Rajesh Kumar
--
Regards
Rajesh 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] IVY comptech????
@Wasif Yes Now this post is Irrelevant to Algogeeks. @Others Discuss about companies and interview Questions at new formed group Interview Street http://groups.google.com/group/interview-street?hl=en else you will be banned without any warnings On Sat, Oct 8, 2011 at 11:31 AM, raj kumar megamonste...@gmail.com wrote: someone please reply -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Attention All Members
Now All of the messages are being Moderated and will be posted on the group only if they are found relevant, any irrelevant post be simply discarded without any notification till percentage of irrelevant posts reduces by a significant amount. if someone is found posting too many irrelevant post, he/she will be banned. Irrelevant Posts 1. Any Company Interview Question (Except Google, Facebook only) 2. Any Code Debugging Post (of type Plz Debug my code You should be able to do it yourself) 3. any kind of C/C++ output question. 4. Any Company related Queries 5. Any Book Requests 6. Any Post having No subjects. (if Subject are there they must be related and Give idea about the post. and again Don't post the complete Question in the subject. it should be posted in the body of the message) + Any OS compiler or other topics unless it requires some good Quality discussion. All the above types of post (Except 6) are now part of new group Interview Street (search Archives for the link). -- 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: another group?
No, 2 Groups will be better because now a days 95% of the mails are regarding companies, rather than mails part most of the people are joining this group only because of this, because they are told by their friends that here most recent Company interview Questions are posted. 1. Most of the Interview Question are Repeated, they are getting Re-Posted with in the gap of 10 days atMax. 2. Most of the Interview Question are easily available on the web with their answer, i don't find any need of discussing them again and again here. 3. and The Most Important part is the reason of creation of this group is not to train people for companies rather to discuss some really good Questions. 4. and about* read and reply to mail you like *part, i don't want them even in my mailbox so that i don't have to decide whether to read it or not. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] can somebody kindly explain what would be the output for the following program
Shiva is right and that is the answer * if you try to change the values in a character array literal, the behavior is undefined* so on some compilers like Turbo C u may get o/p -- 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: rise and fall of power
I also Faced the same problem when i tried this one and when i got to know the mistake it was not very happy :( Use methods powl and log10l instead of pow and log10 and u will get 9 digits of precision :) On Tue, Oct 4, 2011 at 10:21 PM, gaurav yadav gauravyadav1...@gmail.comwrote: nk 34 9: 117566389 23 8: 20880467 92 9: 466101087 1997: 2963208 234232 9: 943982129 3476566 9: 226270832 56999 9: 349261536 9 9: 367879441 567891234 9: 191465113 457474575 9: 278660968 (got these from the comments section.) -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] suggestion
There is a Website that was initiated after the success of its community Algorithms on ORKUT but if i will post the link here people will start spamming there also :P like shady sad :( People have taken this group from Algorithms Group to X_Interview_Questions_Database_Group. seriously Bad :( On Mon, Oct 3, 2011 at 7:54 PM, shady sinv...@gmail.com wrote: people can't even post questions properly same question being asked again and again, so many coders from Russia, Poland, have stopped participating here :-( all discussions are which company ? what is ctc ? what is asked ? what should i do ? if one gets job and then that person becomes immune :-/ seriously lol On Mon, Oct 3, 2011 at 7:50 PM, Ankur Garg ankurga...@gmail.com wrote: Nice Idea but for pulling this you need committed people :) On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan sukrandha...@gmail.comwrote: Hello guys, Here is a suggestion.With so much talented people in this group,why cant we a website that is similar to geeksforgeeks. It will be really helpful to others if all the topics are well organised in the form of website This is just a suggestion.just ignore the message if im wrong or u guys don like the idea -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] suggestion
And About Posting Questions on The Group It is a humble request to the members of the group (who are reading this post) that Please Don't Post Question in the subject of the message. rather put related topic name in the subject, which can give a idea what the question is about. On Mon, Oct 3, 2011 at 8:09 PM, sunny agrawal sunny816.i...@gmail.comwrote: There is a Website that was initiated after the success of its community Algorithms on ORKUT but if i will post the link here people will start spamming there also :P like shady sad :( People have taken this group from Algorithms Group to X_Interview_Questions_Database_Group. seriously Bad :( On Mon, Oct 3, 2011 at 7:54 PM, shady sinv...@gmail.com wrote: people can't even post questions properly same question being asked again and again, so many coders from Russia, Poland, have stopped participating here :-( all discussions are which company ? what is ctc ? what is asked ? what should i do ? if one gets job and then that person becomes immune :-/ seriously lol On Mon, Oct 3, 2011 at 7:50 PM, Ankur Garg ankurga...@gmail.com wrote: Nice Idea but for pulling this you need committed people :) On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan sukrandha...@gmail.comwrote: Hello guys, Here is a suggestion.With so much talented people in this group,why cant we a website that is similar to geeksforgeeks. It will be really helpful to others if all the topics are well organised in the form of website This is just a suggestion.just ignore the message if im wrong or u guys don like the idea -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: rise and fall of power
For Last K Gene has posted the right Approach.
For First K
Hint : Logarithms log(N^N) = NlgN
On Tue, Oct 4, 2011 at 1:14 AM, Gene gene.ress...@gmail.com wrote:
I have not done this, so I'm not sure. But there are some tricks.
You can first break up the computation to exploit repeated squaring.
Rather than n-1 multiplications, you can get away with log_2 n by
computing
n_1 = n^2
n_2 = n_1^2
n_3 = n_2^2
so that n_i = n^{2^i}
for i=1..N where n_N = n and n_{N+1} n
Let b_i be the i'th bit of n.
Then n^n = product_{ i | b_i = 1 } ( n_i )
Now as you say you can't afford to do the full multiply. So you'll
need two arbitrary precision multiplication algorithms keeping k
digits of precision each. The first is easy. Compute n^n as above
modulo 10^k (always throwing away higher order digits) to get the last
k digits.
The high order digits is the tricky part. I think the basic idea is
to implement floating point yourself. I.e. keep k+some extra digits
of mantissa plus an exponent to show where the decimal place is. The
problem is you always need to keep enough extra digits beyond k to be
sure rounding up won't affect to top k. There should be simple
algorithm to determine when you can stop.
Or you can take a chance and count on the fact that the probability of
carry out is limited for each digit, so with about 30 extra digits the
chances are pretty close to zero.
On Oct 3, 8:18 pm, g4ur4v gauravyadav1...@gmail.com wrote:
can anyone please help me on how to approach this problem=
http://www.codechef.com/problems/MARCHA4
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Segment Tree Optimization
implement segment tree with lazy propagation :)
On Tue, Sep 27, 2011 at 1:19 PM, Aamir Khan ak4u2...@gmail.com wrote:
I am trying to solve http://www.spoj.pl/problems/LITE/ using segment tree.
Here's the code but i am getting TLE. Can somebody help me to optimize the
code ?
#includecstdio
#includealgorithm
struct node{
int l;
int r;
bool el ;
node *left;
node *right;
};
struct node *build(int l, int r) {
struct node *root = new node;
root-l = l;
root-r = r;
root-el = 0;
if(l==r) {
root-left=NULL;
root-right=NULL;
return root;
}
root-left = build(l,(l+r)/2);
root-right= build((l+r)/2+1,r);
return root;
}
int query(struct node *root, int l, int r) {
if(root==NULL || rl)
return 0;
if((root-el) (root-l)=l (root-r)=r) {
return (r - l + 1);
}
int mid = (root-l + root-r)/2;
return query(root-left, l, std::min(mid,r)) + query(root-right,
std::max(mid+1,l), r);
}
void update(struct node *root, int l,int r) {
if(root-l==l root-r==r (root-left==NULL || root-el)) {
root-el = 1 - root-el;
return;
}
if(root-el) {
root-left-el = 1;
root-right-el = 1;
root-el = 0;
}
int mid = (root-l + root-r)/2;
if(l = mid)
update(root-left, l, std::min(mid,r));
if(r mid)
update(root-right, std::max(mid+1,l), r);
}
int main() {
int N, M;
scanf(%d %d,N,M);
struct node *root = build(1,N);
int L,R;
int c;
while(M--) {
scanf(%d %d %d\n,c,L,R);
if(c==0)
update(root, L, R);
else
printf(%d\n,query(root,L,R));
}
return 0;
}
Aamir Khan | 3rd Year | Computer Science Engineering | IIT Roorkee
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Sorting:-
I think it can be proved by contradiction that there does not exist a better sorting algorithm than O(mnlogmn) because if there is one then that means we can sort an array better than O(nlgn) by assuming an array as 2D array of k rows and Ceiling(n/k) columns. and if the elements belongs to some range then it may be useful to use Counting or Radix sort depending upon the range On Sat, Sep 24, 2011 at 11:24 PM, siddharth srivastava akssps...@gmail.comwrote: Is the range of numbers provided ? On 24 September 2011 10:26, teja bala pawanjalsa.t...@gmail.com wrote: What is the efficient way to sort a M*N matrix. eg: Given a 3*4 matrix 2 6 7 12 11 8 5 1 9 3 4 10 The ouput should be 1 2 3 4 5 6 7 8 9 10 11 12 Matrix may contain duplicates.. -- 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. -- Regards Siddharth Srivastava -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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: sqrt function...
let x be the number initialize ans to some value like x or x/2 now repeatedly do the following ans = (ans + x/ans)/2 each time you perform this operation you will move closer to the sqrt value and depending upon the precision required stop On Sat, Sep 24, 2011 at 11:17 PM, siddharth srivastava akssps...@gmail.comwrote: On 24 September 2011 13:45, shady sinv...@gmail.com wrote: one of the simplest way is to do binary search... :) +1 On Sat, Sep 24, 2011 at 8:42 PM, teja bala pawanjalsa.t...@gmail.comwrote: http://www.geeksforgeeks.org/archives/3187 check dis one. -- 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. -- Regards Siddharth Srivastava -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 max heap takes O(n) time irrespective of the array being sorted / unsorted.
Read CLRS On Thu, Sep 15, 2011 at 11:51 PM, saurabh agrawal saurabh...@gmail.comwrote: Building a max heap takes O(n) time irrespective of the array being sorted / unsorted. Can someone prove that. I already know that Heap can be constucted in o(n*log(n)) time. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] MS
is it like that all the square should be of same size ? On Tue, Aug 2, 2011 at 11:54 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: Given a rectangle with known width and height, design an algorithm to fill the rectangle using n squares(n is integer given) and make sure in the result the wasting area is minimized. Length of square doesn't have to be integer. i.e, given width=3,height=2,n=5, one solution is that rectangle can be filled with five 1x1 squares and the wasting area is 1. Another solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution. -- Regards, Kamakshi kamakshi...@gmail.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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Sort IT
Radix sort is one of the solution. because this Question is in the section Radix sort in CLRS. :) On Tue, Aug 2, 2011 at 11:10 AM, Ravinder Kumar ravinde...@gmail.comwrote: I have little thought on this : divide the whole array by n and store their remainder also in an array now number in original array are in range 1-n sort the array and when two number with same break the tie using remainder array recreate the array using remainder array . -- *With Regards :* Ravinder Kumar B.Tech Final Year Computer Science and Engineering 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Novell - Algorithms round
can be found in lg(n) using Matrix Exponential method | 1 1 |^n | 1 0 | [f(i) f(i-1)]* |1 1| = [f(i+1) f(i)] |1 0| On Fri, Jul 29, 2011 at 12:05 PM, Reynald reynaldsus...@gmail.com wrote: Write and implement an algorithm to find the nth Fibonacci number, optimized for space and time. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] longest common string!!!!!
String need to be contiguous or not ? On Fri, Jul 29, 2011 at 12:23 PM, AMAN AGARWAL mnnit.a...@gmail.com wrote: please give the solution for this problem... Give an algorithm to find the Longest common string of strings with lengths m,n respectively and also analyse their time complexities -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Novell - Puzzle
No ans will be sum of all final fib. number is the no of she-calves of age 0 second last is number is she-calves of age 1 ...and so on so answer is sum of all On Fri, Jul 29, 2011 at 1:09 PM, Reynald Suz reynaldsus...@gmail.comwrote: Shivnarayan, why should we add all Fibonacci number? Since 1+1 both digits represent the same cow. I think the last Fibonacci is the answer. I'm sorry if I'm wrong. On Fri, Jul 29, 2011 at 12:53 PM, Hemalatha hemalatha.amru...@googlemail.com wrote: @Shivnarayan As per the analysis from the number of cows produced from the she-calves of the 1st cow, I get the foll numbers: 1+2+4+7+11+16+22+29+38+48+59+1(MainCow) = 238. Correct me If am wrong. Regards Hemalatha On Fri, Jul 29, 2011 at 11:45 AM, Reynald reynaldsus...@gmail.comwrote: If a cow produces its first she-calf at age two years and after that produces another single she-calf every year, how many she-calves are there after 12 years? assuming none die. and a similar one, asked to another guy, Suppose a newly-born pair of rabbits, one male, one female, are put in a field. Rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits. Suppose that our rabbits never die and that the female always produces one new pair (one male, one female) every month from the second month on. How many pairs will there be in one year? -- 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. -- Regards Reynald Reni Masters in Software Engineering CIT - India -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] [offtopic] Something to share for those preparing for Amazon Campus Interviews!
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=alg_index On Fri, Jul 29, 2011 at 1:31 PM, Rahul Menon menonrahul1...@gmail.comwrote: @RAHUL SINGHAL Sorry to bother you! Unfortunately I cant find any such links in topcoder. Can you just share a link here! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kgVw78gONbIJ. 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] DS representation.
Array that that stores A,B,C,D,E. it looks like u r on some telephonic interview :P On Fri, Jul 29, 2011 at 3:06 PM, Puneet Gautam puneet.nsi...@gmail.comwrote: Hi, pls tell me which data structure has following representation:: A+Bx+Cx(^2)+Dx(^3)+...+Nx(^n-1).?? reply asap...!! -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] DS representation.
SLL = singly linked list but i think array is better choice :) On Fri, Jul 29, 2011 at 3:36 PM, Puneet Gautam puneet.nsi...@gmail.comwrote: @sunny: well not really in an interview .. its that adobe is coming 1st august to our college.. I found this question in its placement papers..!!! I thought there might be a predefined ds for such representation... What is an SLL..? On 7/29/11, rajeev bharshetty rajeevr...@gmail.com wrote: You can use a Hash map which maps the coefficients of the equation and their exponents. Is this feasible ?? On Fri, Jul 29, 2011 at 3:10 PM, sunny agrawal sunny816.i...@gmail.comwrote: Array that that stores A,B,C,D,E. it looks like u r on some telephonic interview :P On Fri, Jul 29, 2011 at 3:06 PM, Puneet Gautam puneet.nsi...@gmail.comwrote: Hi, pls tell me which data structure has following representation:: A+Bx+Cx(^2)+Dx(^3)+...+Nx(^n-1).?? reply asap...!! -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- Regards Rajeev N B http://www.opensourcemania.co.cc *Winners Don't do Different things , they do things Differently* -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Re : [algogeeks] Re: size of self referential structure
Okay. I was a bit wrongactually the thing is that The exact number of bytes allocated for various C data types depends on *both the machine and the compiler.** *so it may be the that the compiler u are using is 32 bit.. one thing that u can try out is that on ubuntu install 64 bit codeblocks ide. i think u will get size of pointers as 8 bytes. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] puzzle
@Hemlatha this is one of the possible solution the Question is to find Number of such solutions On Thu, Jul 28, 2011 at 12:09 PM, Hemalatha hemalatha.amru...@googlemail.com wrote: Give all the primary and secondary diagonal Elements a value -1 and the rest as 1s. -1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 Regards Hemalatha On Thu, Jul 28, 2011 at 11:29 AM, priyanka goel priya888g...@gmail.comwrote: @ SkRiPt... can u pl explain ur ans? -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] puzzle
yes 2^((n-1)^2) is the answer :) consider a row or column of size n, Number of ways it can we filled with 1's and -1's(such that product is 1) is sum of all nCi where i = 0,2,4. (i = no of -1s) and that will be 2^(n-1) (same is the number when product is -1 ) so now let f(i,j) is the number of ways to fill the matrix of size i,j then f(i,j) = 2^(i-2)*2^(j-2)*f(i-1)(j-1)*2 where f(1,1) = 1; explanation for f(i,j) matrix of size (i,j) can be broken into four parts = matrix of size(i-1,j-1) + jth column of size i-1+ ith row of size (j-1) + element at[i,j] so ans is number of ways matrix [i-1][j-1] can be filled is f(i,j) multiplied with when both row and col are 1 and element is 1 or both row and col are -1 and ele is -1 solving the equation for f(n,n) will give 2^((n-1)^2) @skript my method is little bit complexhow did u arrived at solution.is there a simple way to get to the same answer? On Thu, Jul 28, 2011 at 12:11 PM, sunny agrawal sunny816.i...@gmail.comwrote: @Hemlatha this is one of the possible solution the Question is to find Number of such solutions On Thu, Jul 28, 2011 at 12:09 PM, Hemalatha hemalatha.amru...@googlemail.com wrote: Give all the primary and secondary diagonal Elements a value -1 and the rest as 1s. -1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 Regards Hemalatha On Thu, Jul 28, 2011 at 11:29 AM, priyanka goel priya888g...@gmail.comwrote: @ SkRiPt... can u pl explain ur ans? -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Blocked/Unrolled linked list with no duplicates and sorted
Nice Problem :)
i think taking care of duplicates is very simple...but main point is
sorted insertion
that has to very carefully done
there are many cases that need to be taken care of
1. if the value to be inserted is between two nodes and both nodes are
fullthen a new node will be inserted in the link list and value to be
inserted will be the first element in the new node
case: (1,2)-(4,5) and 3 need to be inserted
after insertion list will be
(1,2)-(3,x)-(4,5)-NULL
2. else the value that need to be inserted will be inside some node...
if there is empty space in the nodesimply insert using insertion sort
(1,2)-(4,x) and 3 is to be inserted, insertion sort in node 2 will suffice
(1,2)-(3,4)-NULL
3. but if the node in which the value need to inserted is full then last
number from that node will be shifted to a new node and then insert the
value in the node.
if array_sz is large the one instead of shifting the last element u can
split into two halves and put first half in first and second in 2nd
(1,2)-(3,5)4 to be inserted
(1,2)-(1,4) -(5,x) -NULL
i think considering these 3 cases would suffice...although first case
can be merged with 3rd if programmed carefully
On Thu, Jul 28, 2011 at 3:35 AM, banu varun.nagp...@gmail.com wrote:
Anyone ?
On Jul 26, 10:27 pm, banu varun.nagp...@gmail.com wrote:
Hi,
Basically I am trying to create a blocked linked list(unrolled linked
list) with following properties
- Configurable number of elements in each node
- No duplicate elements in the unrolled linked list
- Linked list is sorted either during insertion or after creating the
linked list
- In place
Assuming I need to create a sorted unrolled linked list with no
duplicate elements with block size say 2
Example: 10,2,4,2,5,7,9.11,11,5
Final blocked linked list: (2,4)-(5,7)-(9,10)-(11,x) or in reverse
order
Note: x means unutilized location in the array wihtin the node. In
case there are not enough elements to insert in a node, some memory
allocated for a node is unutilized
// Following is node structure
#define ARRAY_SZ 2
typedef struct node
{
struct node* next;
long long int elements[ARRAY_SZ];
long long int elemIndex;
}NODE, *NODE_PTR;
Can you suggest me a way to do this correctly and efficiently? It
could be an pseudo text or C-code.
Thanks
Varun
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] Least Common Ancestor
Solution in the link is for BST, not for BT On Thu, Jul 28, 2011 at 3:15 PM, kavitha nk kavithan...@gmail.com wrote: http://geeksforgeeks.org/?p=1029 follow the link fa one more soln.. //BE COOL// kavi -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Facebook Interview question at NIT Warangal
as Number of possible sets are nCk i think complexity of the best solution will be O(k*nCk) (as in siddarths solution) siddharth's solution will fail in case k 64 a simple recursive program is possible i think in same complexity. On Thu, Jul 28, 2011 at 6:40 PM, Tushar Bindal tushicom...@gmail.comwrote: though the code given by siddharth seems to be a bit tough to understand due to one long statement, it gives a good idea to run the main loop fron 2^k -1 to (2^k - 1)*(2^(n-k)) since these rae the only numbers having k digits set -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Facebook Intern F2F Interview
Okay... i was reading % as Modulus operator :( did u gave the solution Nikhil posted , i think that should be the answer. On Thu, Jul 28, 2011 at 9:10 PM, KK kunalkapadi...@gmail.com wrote: @Nikhil: ya true but i dont know wht else was he expecting. @sunny and Muthu: like suppose u pass 20 then func should return true with 20% probabily and false otherwise... -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] Find the number of solutions.
2 solutions - {1,2}
On Fri, Jul 29, 2011 at 11:10 AM, vaibhav_iiit honeys...@gmail.com wrote:
how many values of x are possible in the following equation.
x^(x^x) - (x^x)^x = 0
where a^b =power(a,b).
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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: binary search tree question!!!!
Node* x = TREE_MINIMUM(root);
for(int i = 0; i k-1; i++){
x = TREE-SUCCESSOR(x);
}
return x;
On Fri, Jul 29, 2011 at 11:08 AM, noobcoder ase.as...@gmail.com wrote:
Iterative inorder of tree till you have traversed k elements. Last
element is the kth smallest.
On Jul 29, 10:10 am, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Please tell the solution of this question
Given a Binary Search Tree, write a program to print the kth smallest
element without using any static/global variable. You can’t pass the
value k
to any function also
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to
continue
that counts!
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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: Amazon Question
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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.
--
regards Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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: MS interview:
There is a Book: Advance Programming in Unix Environment by Richard Stevens
in Chapter 2 i think there is a code that does the job of directory Listing
for given Directory
this is the code - for directory listing
*#include dirent.h
int main(int argc, char *argv[])
{
DIR *dp;
struct dirent *dirp;
if (argc != 2)
err_quit(usage: ls directory_name);
if ((dp = opendir(argv[1])) == NULL)
err_sys(can't open %s, argv[1]);
while ((dirp = readdir(dp)) != NULL)
printf(%s\n, dirp-d_name);
closedir(dp);
exit(0);
}*
for this Question u just need to change this code and use recursion for
directory inside Directories
there are some attributes that are used to identify some object as file,
directory, root directory and parent directory. so in recursion u will take
care for those
On Wed, Jul 27, 2011 at 12:13 PM, geek forgeek geekhori...@gmail.com
wrote:
anyone??
On Tue, Jul 26, 2011 at 11:36 PM, geek forgeek geekhori...@gmail.com
wrote:
Function to display the directory structure in a user friendly way taking
root dir as arg
for a general OS. You may assume and state some basic APIs available in
that OS
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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: Amazon Question
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com
wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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.
--
regards Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] MS interview:
yes Preorder recursion will be good for displaying in User Friendly way... On Wed, Jul 27, 2011 at 12:49 PM, Anand Saha anands...@gmail.com wrote: Implement Preorder Traversal in the File system tree. -- On Wed, Jul 27, 2011 at 12:06 PM, geek forgeek geekhori...@gmail.comwrote: Function to display the directory structure in a user friendly way taking root dir as arg for a general OS. You may assume and state some basic APIs available in that OS -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: Amazon Question
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.com wrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.com
wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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.
--
regards Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: Re : [algogeeks] Re: size of self referential structure
computer architecture !!! 64 bit machine has word size of 8 bytes so pointers are of 8 bytes you never got size as 8 byte because u might be working on a 32 bit machine !! On Wed, Jul 27, 2011 at 2:18 PM, hary rathor harry.rat...@gmail.com wrote: @sunny : what you means by machine dependent means 64 bit: you means by compiler / operating system /computer architecture ? because i never get size of pointer 8 byte. if your statement true then tell me which compiler / operating system /computer architecture i should have get this output 8. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] how to calculate the complexity
Master theorem can be used when we know the recurrence relation. You can read the 2nd Chapter of CLRS.. On Thu, Jul 28, 2011 at 1:16 AM, rajeev bharshetty rajeevr...@gmail.comwrote: Masters Theorem http://en.wikipedia.org/wiki/Master_theorem On Thu, Jul 28, 2011 at 1:14 AM, NITIN SHARMA coolguyinat...@gmail.comwrote: Can anybody explain the basic steps that how to calculate the complexity of an algo so that i would be able to find complexity of any program -- 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. -- Regards Rajeev N B http://www.opensourcemania.co.cc *Winners Don't do Different things , they do things Differently* -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
