Re: [algogeeks] Re: Million Numbers
@ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Million Numbers
@ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Million Numbers
@Balaji: Sorry, the time complexity was not O(log n). It is O(n). On Thu, Jun 9, 2011 at 11:43 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Million Numbers
can anyone explain Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.comwrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.comwrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] SPOJ THRBL
http://www.spoj.pl/problems/THRBL/
my code is
i am getting TLE
# includeiostream
# includecstdio
using namespace std;
//int search(long long int [],long long )
int main()
{
while(1)
{
int n,m;
int count=0;
long long int a[50010]={0};
int b[50010],c[50010];
if((scanf(%d%d,n,m))==EOF)
break;
int i;
for(i=0;in;i++)
cina[i];
for(i=0;im;i++)
cinb[i]c[i];
int j;
int flag=0;
for(i=0;im;i++)
{
for(j=(b[i]-1);j(c[i]-1);j++)
if(a[(b[i]-1)]a[j])
{
flag=1;
break;
}
if(flag==0)
count++;
flag=0;
}
coutcountendl;
}
return 0;
}
why i am getting TLE...can anyone explain
this...plzz
--
*WITH REGARDS,*
*
*
*KARTIK SACHAN*
*B.TECH 2ND YEAR*
*COMPUTER SCIENCE AND ENGINEERING*
*NIT 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.
Re: [algogeeks] Re: Million Numbers
Lets say we have 9 numbers from 1 to 10 and one number is missing. We hv a RAM which can accomodate only 3 nos. 9,6,7,4,3,2,1,5,10 So, we split the file into 3 smaller files each containing 3 nos. File1: 9,6,7 File2: 4,3,2 File3: 1,5,10 Now take each file into memory one by one and min heapify them and put them back in the memory. File1: 6,9,7 File2: 2,3,4 File3: 1,5,10 The 1st element in each file is min in each file. Now make a file temp containing the 1st element of each file and remove the 1st element from the files 1,2 and 3.Min heapify each file.. Temp: 1,6,2 File1: 7,9 File2: 3,4 File3: 5,10 Now remove 1 from file Temp and take element from File3 because 1 belonged to File3 originally. Again min Heapify them. Temp: 2,6,5 File1: 7,9 File2: 3,4 File3: 10 Now remove 2 Temp: 3,5,6 File1: 7,9 File2: 4 File3: 10 Now remove 3 Temp: 4,6,5 File1: 7,9 File2: File3: 10 Now going on this way we will find that after we remove 7, we could not find 8. So, 8 is the missing no. Ankit Sambyal BITS Pilani On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa varunpahwa2...@gmail.com wrote: can anyone explain Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.com wrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Million Numbers
@ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.comwrote: Lets say we have 9 numbers from 1 to 10 and one number is missing. We hv a RAM which can accomodate only 3 nos. 9,6,7,4,3,2,1,5,10 So, we split the file into 3 smaller files each containing 3 nos. File1: 9,6,7 File2: 4,3,2 File3: 1,5,10 Now take each file into memory one by one and min heapify them and put them back in the memory. File1: 6,9,7 File2: 2,3,4 File3: 1,5,10 The 1st element in each file is min in each file. Now make a file temp containing the 1st element of each file and remove the 1st element from the files 1,2 and 3.Min heapify each file.. Temp: 1,6,2 File1: 7,9 File2: 3,4 File3: 5,10 Now remove 1 from file Temp and take element from File3 because 1 belonged to File3 originally. Again min Heapify them. Temp: 2,6,5 File1: 7,9 File2: 3,4 File3: 10 Now remove 2 Temp: 3,5,6 File1: 7,9 File2: 4 File3: 10 Now remove 3 Temp: 4,6,5 File1: 7,9 File2: File3: 10 Now going on this way we will find that after we remove 7, we could not find 8. So, 8 is the missing no. Ankit Sambyal BITS Pilani On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa varunpahwa2...@gmail.com wrote: can anyone explain Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.com wrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] Re: Million Numbers
@Balaji : No, I didn't miss it. Since we had broken the file containing 300 million integers into smaller files containing much less numbers. So, the time complexity of min heapify is not O(logn), but it is O(log(no. of numbers in smaller file)), which is constant. Correct if I am wrong. On Fri, Jun 10, 2011 at 12:39 AM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.com wrote: Lets say we have 9 numbers from 1 to 10 and one number is missing. We hv a RAM which can accomodate only 3 nos. 9,6,7,4,3,2,1,5,10 So, we split the file into 3 smaller files each containing 3 nos. File1: 9,6,7 File2: 4,3,2 File3: 1,5,10 Now take each file into memory one by one and min heapify them and put them back in the memory. File1: 6,9,7 File2: 2,3,4 File3: 1,5,10 The 1st element in each file is min in each file. Now make a file temp containing the 1st element of each file and remove the 1st element from the files 1,2 and 3.Min heapify each file.. Temp: 1,6,2 File1: 7,9 File2: 3,4 File3: 5,10 Now remove 1 from file Temp and take element from File3 because 1 belonged to File3 originally. Again min Heapify them. Temp: 2,6,5 File1: 7,9 File2: 3,4 File3: 10 Now remove 2 Temp: 3,5,6 File1: 7,9 File2: 4 File3: 10 Now remove 3 Temp: 4,6,5 File1: 7,9 File2: File3: 10 Now going on this way we will find that after we remove 7, we could not find 8. So, 8 is the missing no. Ankit Sambyal BITS Pilani On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa varunpahwa2...@gmail.com wrote: can anyone explain Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.com wrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
[algogeeks]
There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] [brain teaser ] Find next number in series 10 june
42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Find next number in series * * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-series-10-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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]
can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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.
Re: [algogeeks] SPOJ THRBL
@Karthik : Can you please the logic ??. Would be nice ..
On Fri, Jun 10, 2011 at 12:42 PM, kartik sachan kartik.sac...@gmail.comwrote:
http://www.spoj.pl/problems/THRBL/
my code is
i am getting TLE
# includeiostream
# includecstdio
using namespace std;
//int search(long long int [],long long )
int main()
{
while(1)
{
int n,m;
int count=0;
long long int a[50010]={0};
int b[50010],c[50010];
if((scanf(%d%d,n,m))==EOF)
break;
int i;
for(i=0;in;i++)
cina[i];
for(i=0;im;i++)
cinb[i]c[i];
int j;
int flag=0;
for(i=0;im;i++)
{
for(j=(b[i]-1);j(c[i]-1);j++)
if(a[(b[i]-1)]a[j])
{
flag=1;
break;
}
if(flag==0)
count++;
flag=0;
}
coutcountendl;
}
return 0;
}
why i am getting TLE...can anyone explain
this...plzz
--
*WITH REGARDS,*
*
*
*KARTIK SACHAN*
*B.TECH 2ND YEAR*
*COMPUTER SCIENCE AND ENGINEERING*
*NIT 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.
--
Thanks Regards
Abhishek Iyer
If You Obey All the Rules, You Will Miss All the Fun.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 THRBL
what i understand from the problem was that.
n no of higests are given
and a and b and city no i.e from city a a ball is thrown to city no b
so i have done
from array a[] i.e hieght { n...no of times}
find all the element between b[i].city A and
c[i]city B
then check IF value of b[i] is greater than all the element occur between
them if yes then count++
else count remain same
if any thing worng plzz expain
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Re: MS Interview
Nothing is specified but lets take it as 2MB ram On Jun 10, 10:14 am, hary rathor harry.rat...@gmail.com wrote: dumnanshu you should first mention memory size in your computer so that i could know that how many number i can have in main memory at 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.
Re: [algogeeks]
but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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]
@Sunny I am assuming that the tree is rooted. There is no 'parent' pointer. A / \ B C* / \ D* F* / \ J K / \ M* suppose x=D, y=C, z=F According to you, finding the lca of x and z= A Now y lies on path from lca to z, but it doesn't lie on path from x to z. Am I missing something? On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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.
Re: [algogeeks]
thats why i mentioned x OR z and i m considering parent pointer :) without parent pointer both solutions will be O(n) :) On Fri, Jun 10, 2011 at 3:02 PM, Harshal hc4...@gmail.com wrote: @Sunny I am assuming that the tree is rooted. There is no 'parent' pointer. A / \ B C* / \ D* F* / \ J K / \ M* suppose x=D, y=C, z=F According to you, finding the lca of x and z= A Now y lies on path from lca to z, but it doesn't lie on path from x to z. Am I missing something? On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.comwrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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.
[algogeeks] Re: Million Numbers
Hey the file has random 300 million numbers (9 digit)...there might be duplicates... not a particular sequence out of the many missing numbers we have to print just one... someone please try to understand the solution given alongwith the question. On Jun 10, 12:49 pm, ankit sambyal ankitsamb...@gmail.com wrote: @Balaji : No, I didn't miss it. Since we had broken the file containing 300 million integers into smaller files containing much less numbers. So, the time complexity of min heapify is not O(logn), but it is O(log(no. of numbers in smaller file)), which is constant. Correct if I am wrong. On Fri, Jun 10, 2011 at 12:39 AM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.com wrote: Lets say we have 9 numbers from 1 to 10 and one number is missing. We hv a RAM which can accomodate only 3 nos. 9,6,7,4,3,2,1,5,10 So, we split the file into 3 smaller files each containing 3 nos. File1: 9,6,7 File2: 4,3,2 File3: 1,5,10 Now take each file into memory one by one and min heapify them and put them back in the memory. File1: 6,9,7 File2: 2,3,4 File3: 1,5,10 The 1st element in each file is min in each file. Now make a file temp containing the 1st element of each file and remove the 1st element from the files 1,2 and 3.Min heapify each file.. Temp: 1,6,2 File1: 7,9 File2: 3,4 File3: 5,10 Now remove 1 from file Temp and take element from File3 because 1 belonged to File3 originally. Again min Heapify them. Temp: 2,6,5 File1: 7,9 File2: 3,4 File3: 10 Now remove 2 Temp: 3,5,6 File1: 7,9 File2: 4 File3: 10 Now remove 3 Temp: 4,6,5 File1: 7,9 File2: File3: 10 Now going on this way we will find that after we remove 7, we could not find 8. So, 8 is the missing no. Ankit Sambyal BITS Pilani On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa varunpahwa2...@gmail.com wrote: can anyone explain Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.com wrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another
Re: [algogeeks] [brain teaser ] Find next number in series 10 june
42, 49 2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com 42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Find next number in series * * *** * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-series-10-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
@sunny agarwal : i dont think, it is O(lgn) its not a BST and further u need to check for existence of y in the path from lca to x or lca to z., so it l be O(n).. On Jun 10, 1:57 pm, sunny agrawal sunny816.i...@gmail.com wrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.comwrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
[algogeeks] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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]
@ross if a parent pointer is there lca can be found in lgn and path can be traversed in lgn too why it cannot be lgn what is the problem ?? On Fri, Jun 10, 2011 at 3:06 PM, sunny agrawal sunny816.i...@gmail.comwrote: thats why i mentioned x OR z and i m considering parent pointer :) without parent pointer both solutions will be O(n) :) On Fri, Jun 10, 2011 at 3:02 PM, Harshal hc4...@gmail.com wrote: @Sunny I am assuming that the tree is rooted. There is no 'parent' pointer. A / \ B C* / \ D* F* / \ J K / \ M* suppose x=D, y=C, z=F According to you, finding the lca of x and z= A Now y lies on path from lca to z, but it doesn't lie on path from x to z. Am I missing something? On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.com wrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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 -- 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] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
First algorithm taht comes in mind deque a element if +ve enque again if(-ve) do nothing now question is terminating condition On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] [brain teaser ] Find next number in series 10 june
@ankur..how did you get that...explain..plz On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.comwrote: 42, 49 2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com 42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Find next number in series * * *** * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-series-10-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
initialy cal size of queue then apply a for loop On Fri, Jun 10, 2011 at 4:00 PM, sunny agrawal sunny816.i...@gmail.comwrote: First algorithm taht comes in mind deque a element if +ve enque again if(-ve) do nothing now question is terminating condition On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] SPOJ THRBL
i agree with the logici also implemented it...and getting TLE...there
must exist some better method :(
On Fri, Jun 10, 2011 at 2:18 AM, kartik sachan kartik.sac...@gmail.comwrote:
what i understand from the problem was that.
n no of higests are given
and a and b and city no i.e from city a a ball is thrown to city no b
so i have done
from array a[] i.e hieght { n...no of times}
find all the element between b[i].city A and
c[i]city B
then check IF value of b[i] is greater than all the element occur between
them if yes then count++
else count remain same
if any thing worng plzz expain
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
@sunny finding lca in logn is fine, but how can we traverse the path in logn.. ? On Fri, Jun 10, 2011 at 3:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: @ross if a parent pointer is there lca can be found in lgn and path can be traversed in lgn too why it cannot be lgn what is the problem ?? On Fri, Jun 10, 2011 at 3:06 PM, sunny agrawal sunny816.i...@gmail.comwrote: thats why i mentioned x OR z and i m considering parent pointer :) without parent pointer both solutions will be O(n) :) On Fri, Jun 10, 2011 at 3:02 PM, Harshal hc4...@gmail.com wrote: @Sunny I am assuming that the tree is rooted. There is no 'parent' pointer. A / \ B C* / \ D* F* / \ J K / \ M* suppose x=D, y=C, z=F According to you, finding the lca of x and z= A Now y lies on path from lca to z, but it doesn't lie on path from x to z. Am I missing something? On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.com wrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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 -- 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,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 THRBL
how should we get TLE loop total running less than 10^6?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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]
using parent pointers untill we reach to lca. On Fri, Jun 10, 2011 at 3:59 PM, aanchal goyal goyal.aanch...@gmail.comwrote: @sunny finding lca in logn is fine, but how can we traverse the path in logn.. ? On Fri, Jun 10, 2011 at 3:50 PM, sunny agrawal sunny816.i...@gmail.comwrote: @ross if a parent pointer is there lca can be found in lgn and path can be traversed in lgn too why it cannot be lgn what is the problem ?? On Fri, Jun 10, 2011 at 3:06 PM, sunny agrawal sunny816.i...@gmail.comwrote: thats why i mentioned x OR z and i m considering parent pointer :) without parent pointer both solutions will be O(n) :) On Fri, Jun 10, 2011 at 3:02 PM, Harshal hc4...@gmail.com wrote: @Sunny I am assuming that the tree is rooted. There is no 'parent' pointer. A / \ B C* / \ D* F* / \ J K / \ M* suppose x=D, y=C, z=F According to you, finding the lca of x and z= A Now y lies on path from lca to z, but it doesn't lie on path from x to z. Am I missing something? On Fri, Jun 10, 2011 at 2:50 PM, sunny agrawal sunny816.i...@gmail.com wrote: but that will be O(n) i think On Fri, Jun 10, 2011 at 2:38 PM, Harshal hc4...@gmail.com wrote: can be solved using dfs. On Fri, Jun 10, 2011 at 2:27 PM, sunny agrawal sunny816.i...@gmail.com wrote: find common Ancestor of both. see if y lies on path from x or z to this ancestor O(lgn) On Fri, Jun 10, 2011 at 1:20 PM, aanchal goyal goyal.aanch...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, 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 -- 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,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] [brain teaser ] Find next number in series 10 june
may be 42,47. actually table of seven and a digit 7. On Fri, Jun 10, 2011 at 3:29 AM, nicks crazy.logic.k...@gmail.com wrote: @ankur..how did you get that...explain..plz On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.comwrote: 42, 49 2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com 42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Find next number in series * * *** * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-series-10-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: solve the series
@sunny. ..lol..dude..20 June is My Bro's B'day 18th Nov is of My mom ...:P Shashank Computer Science Engg. Birla Institute of Technology, Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: [brain teaser ] Find next number in series 10 june
42,50 On Jun 10, 3:29 pm, nicks crazy.logic.k...@gmail.com wrote: @ankur..how did you get that...explain..plz On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.comwrote: 42, 49 2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com 42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Find next number in series * * *** * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-seri... Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: [brain teaser ] Find next number in series 10 june
42,47 On Fri, Jun 10, 2011 at 4:50 PM, abhishekriyer abhishekr.iye...@gmail.comwrote: 42,50 On Jun 10, 3:29 pm, nicks crazy.logic.k...@gmail.com wrote: @ankur..how did you get that...explain..plz On Fri, Jun 10, 2011 at 3:11 AM, ankur aggarwal aggarwal11...@gmail.com wrote: 42, 49 2011/6/10 • » νιρυℓ « • vipulmehta.1...@gmail.com 42, 47 just guessing according to the pattern. On Fri, Jun 10, 2011 at 1:37 PM, Lavesh Rawat lavesh.ra...@gmail.com wrote: *Find next number in series * * *** * * ** *What are the next two numbers in this sequence? 7, 14, 17, 21, 27, 28, 35, 37, ?, ? * * * *Update Your Answers at* : Click Here http://dailybrainteaser.blogspot.com/2011/06/find-next-number-in-seri... Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] SPOJ THRBL
Use Range Maximum Query. On Fri, Jun 10, 2011 at 4:15 PM, kartik sachan kartik.sac...@gmail.comwrote: how should we get TLE loop total running less than 10^6?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
Yups...that seems best.. :) On Fri, Jun 10, 2011 at 4:03 PM, sunny agrawal sunny816.i...@gmail.comwrote: initialy cal size of queue then apply a for loop On Fri, Jun 10, 2011 at 4:00 PM, sunny agrawal sunny816.i...@gmail.comwrote: First algorithm taht comes in mind deque a element if +ve enque again if(-ve) do nothing now question is terminating condition On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.comwrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 THRBL
u construct a tree nlogn , every node answers a query.. (or u get ans with a recursion) in log(n) , so when u r doing a lot of query RMQ proves to be very fast On Fri, Jun 10, 2011 at 6:28 PM, nicks crazy.logic.k...@gmail.com wrote: ya i saw that in the comments on spoj someone suggested to use RMQcan you explain a bit moe how to implement RMQ and how it is helping in reducing the time !! On Fri, Jun 10, 2011 at 5:53 AM, saurabh singh saurab...@gmail.comwrote: Use Range Maximum Query. On Fri, Jun 10, 2011 at 4:15 PM, kartik sachan kartik.sac...@gmail.comwrote: how should we get TLE loop total running less than 10^6?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] SPOJ THRBL
Suppose you are given an array a[]={2,3,1,4,6,7,10}
now for successfully transferring the ball,from ith city to jth city,a[i]
max(a[i..j-1]).
A naive approach would be to calculate all possible max[i][j] that is max
for each interval and then answer the query in 0(1) time.Another approach
would be to divide the array into powers of 2 and find the max for each
divided interval.Then answer each query in log n time..Finally you can
construct
a b tree with root node having the max of the array,the left and right child
having max of respectively max(a[0..i/2]) and max(a[i/2+1..i]) and so
on.Then answer each query in log(n) time for searching the right
interval
So if
On Fri, Jun 10, 2011 at 6:28 PM, nicks crazy.logic.k...@gmail.com wrote:
ya i saw that in the comments on spoj someone suggested to use RMQcan
you explain a bit moe how to implement RMQ and how it is helping in reducing
the time !!
On Fri, Jun 10, 2011 at 5:53 AM, saurabh singh saurab...@gmail.comwrote:
Use Range Maximum Query.
On Fri, Jun 10, 2011 at 4:15 PM, kartik sachan
kartik.sac...@gmail.comwrote:
how should we get TLE loop total running less than 10^6??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
[algogeeks] Reverse the bits.
How do you reverse the bits between j to k in a 32 bit integer. For e.g.: n = 11100011; j = 2 and k = 5 output: 1101 (bits from 2 to 5 are reversed.) n = 11010110; j = 1 and k = 5 output: 11101000 O(1) method is preferred. Thanks, -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
since a queue is given ...only queue operations are allowed just dequeue all elements from the queue and if a number is +ve enqueue them to other queue after this just copy the 2nd queue to 1st one O(n) On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Aditya Kumar B-tech 3rd year Computer Science Engg. 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.
Re: [algogeeks] C Question
anything that is declared volatilecompiler dont apply its optimization on that storage i.e it dont remove the redundant memory accesses in case of a normal volatile variable ,its value is checked everytime it is used in the program compiler dont make any assumptions similarly in case of volatile pointer ,its address is checked everytime it is derefrenced On Thu, Jun 9, 2011 at 10:36 PM, shashankreddy509 shashankreddy...@gmail.com wrote: @Aditya:- can u give a brief intro of volatile pointer. Thanks. -- 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/-/SJkBkvK-MqAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Aditya Kumar B-tech 3rd year Computer Science Engg. 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.
[algogeeks] Print 1 to n without loops
Take n from user and print 1 to n. No loops like for/while/do-while are allowed to use. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] FOR ALL INDIANS PLZ READ IT
so what ? supporting anna hazare is not a bad idea. On Thu, Jun 9, 2011 at 12:54 PM, Naveen Kumar naveenkumarve...@gmail.comwrote: There is no such condition put up by the govt. If you give a missed call you are showing your support to Anna Hazare Please read http://theindiapost.com/delhi/support-hazare-give-call-02261550789/ On Thu, Jun 9, 2011 at 12:15 PM, Abdul Rahman Shariff ears7...@gmail.comwrote: did u try it ?? nd did u get the msg?? On Thu, Jun 9, 2011 at 1:06 AM, kartik sachan kartik.sac...@gmail.comwrote: Frnz govt of india has put a condition dat lokpal bill will b implemented if 25 crore ppl spport it. plz give a miss kol(free) to 02261550789 .kol ends itself n u ll get a msg rply. Plz support against corruption... -- *WITH REGARDS,* * * *KARTIK SACHAN* *B.TECH 2ND YEAR* *COMPUTER SCIENCE AND ENGINEERING* *NIT 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. -- Ehab Abdul Rahman Shariff -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 explain this problem
just visit spoj forums On Fri, Jun 10, 2011 at 9:42 AM, keyan karthi keyankarthi1...@gmail.comwrote: the nos can repeat :) ie the valid set may contain multiple instance of a same number.. hope this helps :) On Fri, Jun 10, 2011 at 9:31 AM, saurabh singh saurab...@gmail.comwrote: Problem link- ABCDEF https://www.spoj.pl/problems/ABCDEF/ Can someone please explain this problem.The problem says a,b,c,d,e,f belongs to S.But what if size of S is smaller than 6? I know i am missing sumthing very trivialhelp plz. -- 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Aditya Kumar B-tech 3rd year Computer Science Engg. 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.
[algogeeks] Re: MS Interview
ex-or operation on all the elements give you the answer.
On Jun 9, 5:45 am, Dumanshu duman...@gmail.com wrote:
Q1. I have a file in which there are supposed to be 4 billion
numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is
missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number.
Q2. I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one
element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] write an algo that deletes all negative integers without changing the order of remaining elements of the queue
I think you don't need other queue to do this, simply enqueue the non-negative dequeued element to the original queue. On Fri, Jun 10, 2011 at 11:32 AM, ADITYA KUMAR aditya...@gmail.com wrote: since a queue is given ...only queue operations are allowed just dequeue all elements from the queue and if a number is +ve enqueue them to other queue after this just copy the 2nd queue to 1st one O(n) On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Print 1 to n without loops
Can goto statement be used? On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.comwrote: Take n from user and print 1 to n. No loops like for/while/do-while are allowed to use. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Jyothi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Print 1 to n without loops
IF allowed ??? If yes...Use recursion.. On Fri, Jun 10, 2011 at 9:12 PM, Navneet Gupta navneetn...@gmail.comwrote: Take n from user and print 1 to n. No loops like for/while/do-while are allowed to use. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Print 1 to n without loops
No. On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti nagajyothi.gu...@gmail.com wrote: Can goto statement be used? On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.comwrote: Take n from user and print 1 to n. No loops like for/while/do-while are allowed to use. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Jyothi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Print 1 to n without loops
Using recursion would be like using loops only. Also i believe the recursion used would be tail recursion and one can change tail recursion to loop based non recursive method. Okay, giving all a hint. Think classes and objects. On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta navneetn...@gmail.comwrote: No. On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti nagajyothi.gu...@gmail.com wrote: Can goto statement be used? On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.comwrote: Take n from user and print 1 to n. No loops like for/while/do-while are allowed to use. --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Jyothi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Print 1 to n without loops
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this will print from 1 to 5
am i right?
On Fri, Jun 10, 2011 at 9:30 PM, Navneet Gupta navneetn...@gmail.comwrote:
Using recursion would be like using loops only. Also i believe the
recursion used would be tail recursion and one can change tail recursion to
loop based non recursive method.
Okay, giving all a hint. Think classes and objects.
On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta navneetn...@gmail.comwrote:
No.
On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti
nagajyothi.gu...@gmail.com wrote:
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta
navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Jyothi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--Navneet
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
radhika .. :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Print 1 to n without loops
Good Answer Radhika. You are correct.
On Fri, Jun 10, 2011 at 9:40 PM, Radhika Renganathan
radi.coo...@gmail.comwrote:
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this will print from 1 to 5
am i right?
On Fri, Jun 10, 2011 at 9:30 PM, Navneet Gupta navneetn...@gmail.comwrote:
Using recursion would be like using loops only. Also i believe the
recursion used would be tail recursion and one can change tail recursion to
loop based non recursive method.
Okay, giving all a hint. Think classes and objects.
On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta navneetn...@gmail.comwrote:
No.
On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti
nagajyothi.gu...@gmail.com wrote:
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta
navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Jyothi
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--Navneet
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
radhika .. :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Print 1 to n without loops
sorry i meant 'constructor' !
On Fri, Jun 10, 2011 at 9:40 PM, Radhika Renganathan
radi.coo...@gmail.comwrote:
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this will print from 1 to 5
am i right?
On Fri, Jun 10, 2011 at 9:30 PM, Navneet Gupta navneetn...@gmail.comwrote:
Using recursion would be like using loops only. Also i believe the
recursion used would be tail recursion and one can change tail recursion to
loop based non recursive method.
Okay, giving all a hint. Think classes and objects.
On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta navneetn...@gmail.comwrote:
No.
On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti
nagajyothi.gu...@gmail.com wrote:
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta
navneetn...@gmail.comwrote:
Take n from user and print 1 to n. No loops like for/while/do-while are
allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Jyothi
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--Navneet
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
radhika .. :)
--
radhika .. :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Print 1 to n without loops
this problem was discussed some time before on this group
i am picking up a solution discussed there which you would love to see
int i=1;
#define PRINT1 couti++endl;
#define PRINT2 PRINT1 PRINT1
#define PRINT4 PRINT2 PRINT2
#define PRINT8 PRINT4 PRINT4
#define PRINT16 PRINT8 PRINT8
#define PRINT32 PRINT16 PRINT16
#define PRINT64 PRINT32 PRINT32
int main()
{
//as 100 = (1100100); we need to use PRINT64, PRINT32, and PRINT4
PRINT64;
PRINT32;
PRINT4;
}
This will print 1 to 100. You can use this code to print from 1 to x
(x=128). You can extend it to larger numbers, by adding PRINT128,
PRINT256...etc.
i appreciate the radikha's solution...it was discussed there also and is
better :)
On Fri, Jun 10, 2011 at 9:15 AM, Radhika Renganathan
radi.coo...@gmail.comwrote:
sorry i meant 'constructor' !
On Fri, Jun 10, 2011 at 9:40 PM, Radhika Renganathan
radi.coo...@gmail.com wrote:
we can declare a class with construction printing value
class A
{
private:
static int i;
public:
A()
{
cout++i endl;
}
};
A::i=0;
main()
{
int n=5;
A ob[n];
}
this will print from 1 to 5
am i right?
On Fri, Jun 10, 2011 at 9:30 PM, Navneet Gupta navneetn...@gmail.comwrote:
Using recursion would be like using loops only. Also i believe the
recursion used would be tail recursion and one can change tail recursion to
loop based non recursive method.
Okay, giving all a hint. Think classes and objects.
On Fri, Jun 10, 2011 at 9:26 PM, Navneet Gupta navneetn...@gmail.comwrote:
No.
On Fri, Jun 10, 2011 at 9:26 PM, nagajyothi gunti
nagajyothi.gu...@gmail.com wrote:
Can goto statement be used?
On Fri, Jun 10, 2011 at 11:42 AM, Navneet Gupta navneetn...@gmail.com
wrote:
Take n from user and print 1 to n. No loops like for/while/do-while
are allowed to use.
--Navneet
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Jyothi
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--Navneet
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
radhika .. :)
--
radhika .. :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] searching a number in circular sorted array
hi frndz given an array which is circularly sorted like 6 ,7,8 ,1 ,2 ,3 ,4,5 search a given number. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: [brain teaser ] Find next number in series 10 june
42,47 -- 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/-/mi5D7Az5nssJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Reverse the bits.
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.com wrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] C Question
@Aditya; Thanks.. -- 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/-/UO6vAXBXhXEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Reverse the bits.
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.comwrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
[algogeeks] Re: searching a number in circular sorted array
Use ternary search to find the minimum number. (In this case 1) Then you have two sorted arrays, one ascending and one descending. Now, you can apply binary search. First, check the number with the last element and the first element and chose the appropriate array for searching. Time complexity: O(log n) Space complexity: O(1). On Jun 10, 9:06 pm, coder dumca coder.du...@gmail.com wrote: hi frndz given an array which is circularly sorted like 6 ,7 ,8 ,1 ,2 ,3 ,4 ,5 search a given number. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Puzzle
@ross: seems logically correct..nice solution.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: write an algo that deletes all negative integers without changing the order of remaining elements of the queue
Y do we need to deque and enque the nodes again the problem is similar to the node given in the linked list and delete that node. solution is : copy the next node data to the node to be deleted(ie node holding -ve number) and delete the next node. in this way order won't be changed. Correct me if i am wrong On Jun 10, 3:14 pm, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: write an algo that deletes all negative integers without changing the order of remaining elements of the queue
in this question i assumed that we need to write a function which takes an input a queue and function implements the required. we don't know how the queue is implemented, means we don't know about structure of the node. only 2 standard functions of queue enqueue and dequeue are known On Fri, Jun 10, 2011 at 11:16 PM, scifi vibhu.bitspil...@gmail.com wrote: Y do we need to deque and enque the nodes again the problem is similar to the node given in the linked list and delete that node. solution is : copy the next node data to the node to be deleted(ie node holding -ve number) and delete the next node. in this way order won't be changed. Correct me if i am wrong On Jun 10, 3:14 pm, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: [brain teaser ] Find next number in series 10 june
42, 47 On Fri, Jun 10, 2011 at 9:57 PM, shashankreddy509 shashankreddy...@gmail.com wrote: 42,47 -- 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/-/mi5D7Az5nssJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MS Interview
@ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: searching a number in circular sorted array
Binary search is sufficient for this particular case.
To help the explain, we assume the circular sorted array is ascending if
probably rotated. we use *d[0..n - 1]* to represent the array
with n elements and *v* to represent the searched number.
Observing the circular sorted sequence d[0..n - 1]:
6 ,7,8 ,1 ,2 ,3 ,4,5
we can find that:
1) d[0] = d[n - 1]
2) there exists one x that d[0..x] is ascending and d[x + 1.. n - 1] is also
ascending
Using the rules above, we can simply get an binary search algorithm:
The C++ code is below:
http://fayaa.com/code/view/20170/
*C++语言*: Codee#20170 http://fayaa.com/code/view/20170/
#include cstdio
using namespace std;
// Parameters:
// @d: is one circularly sorted array, it looks like 6, 7, 8, 1, 2, 3, 5, 6
// @v: is the searched number
// Returns: -1 if not found or return the index
int BinarySearch(int d[], int len, int v)
{
if(d == NULL || len = 0)
return -1;
int left = 0, right = len - 1;
while(right - left 1)
{
int mid = (left + right) 1;
if(d[mid] = d[left])
{
if(v = d[mid])
left = mid;
else if(v = d[left])
right = mid;
else
left = mid;
}
else // d[mid] d[left]
{
if(v d[mid])
right = mid;
else if(v d[left])
left = mid;
else
right = mid;
}
}
if(d[left] != v)
return -1;
return left;
}
int main()
{
int d[] = {6, 7, 8, 1, 2, 3, 4, 5};
for(int i = 0; i 10; i++)
{
printf(%d: %d\n, i, BinarySearch(d, 8, i));
}
return 0;
}
2011/6/11 L prnk.bhatna...@gmail.com
Use ternary search to find the minimum number. (In this case 1)
Then you have two sorted arrays, one ascending and one descending.
Now, you can apply binary search. First, check the number with the
last element and the first element and chose the appropriate array for
searching.
Time complexity: O(log n)
Space complexity: O(1).
On Jun 10, 9:06 pm, coder dumca coder.du...@gmail.com wrote:
hi frndz
given an array which is circularly sorted like
6 ,7,8 ,1 ,2 ,3 ,4,5
search a given number.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] HASHIT
This is the link to the SPOJ problem HASHIT :
http://www.spoj.pl/problems/HASHIT/
i donno whts the mistake... i keep getting wrong answer even though
the Q is Straightforward :(
#includeiostream
#includestring
using namespace std;
int hash(string str)
{
int sum = 0;
int len = str.size();
for(int i=0; ilen; i++)
sum = (sum + (i+1)*str[i]) % 101;
sum = (sum * 19) % 101;
return sum;
}
void add(string *array, string str, int count)
{
//cout string received: str endl;
int key = hash(str), pos;
for(int j=0; j=19; j++)
{
pos = (key + j*j + 23*j) % 101;
if(array[pos] == )
{
//cout Added endl;
array[pos] = str;
count++;
return;
}
else if(array[pos] == str)
return;
}
}
void d(string *array, string str, int count)
{
//cout string received: str endl;
int key = hash(str), pos;
for(int j=0; j=19; j++)
{
pos = (key + j*j + 23*j) % 101;
if(array[pos] == str)
{
//cout Deleted endl;
array[pos] = ;
count--;
return;
}
}
}
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
int t;
cin t;
while(t--)
{
int n, count = 0;
string array[101], temp;
for(int i=0; i101; i++)
array[i] = ;
cin n;
while(n--)
{
cin temp;
string opr = temp.substr(0, 3);
if(opr == ADD)
add(array, temp.substr(4, temp.size() - 4), count);
else
d(array, temp.substr(4, temp.size() - 4), count);
}
cout count endl;
for(int i=0; i101; i++)
{
if(array[i] != )
cout i : array[i] endl;
}
}
//system(pause);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: SPOJ THRBL
Search Topcoder Tutorial Range Minimum Query @ Google... By few intuitive changes u can implement Range Maximum Query as well... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: MS Interview
@kunal: could u plz explan ur XOR approach by using a small set of numbers. lets say we have numbers from 1 to 5 and one number is missing. so u mean 1 XOR 2 XOR 4 XOR 5 would give me 3??? On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote: @ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: MS Interview
@kunal... yeah it will work. thnx :) On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote: @ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: write an algo that deletes all negative integers without changing the order of remaining elements of the queue
We know the size (number of elements) of the queue right? On Jun 10, 1:33 pm, ADITYA KUMAR aditya...@gmail.com wrote: @monang wats the terminating codition..?? On Fri, Jun 10, 2011 at 9:21 PM, Monang Setyawan mon...@gmail.com wrote: I think you don't need other queue to do this, simply enqueue the non-negative dequeued element to the original queue. On Fri, Jun 10, 2011 at 11:32 AM, ADITYA KUMAR aditya...@gmail.com wrote: since a queue is given ...only queue operations are allowed just dequeue all elements from the queue and if a number is +ve enqueue them to other queue after this just copy the 2nd queue to 1st one O(n) On Fri, Jun 10, 2011 at 3:44 PM, Sangeeta sangeeta15...@gmail.com wrote: write an algo that deletes all negative integers without changing the order of remaining elements of the queue -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. 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.
Re: [algogeeks] [brain teaser ] Famous Probability puzzle SHOOT
Mr. White On Wed, Jun 8, 2011 at 8:07 PM, amit kumar amitthecoo...@gmail.com wrote: Mr. White On Wed, Jun 8, 2011 at 2:30 PM, nicks crazy.logic.k...@gmail.com wrote: what does the highest chance of survival ? mean.. is it about black's survival or overall survival.i'm confused On Wed, Jun 8, 2011 at 1:33 AM, DeVaNsH gUpTa devanshgupta...@gmail.comwrote: In the air without aiming any of the two. On 6/8/11, Lavesh Rawat lavesh.ra...@gmail.com wrote: *Famous Probability puzzle shoot * * * ** *Mr. Black, Mr. Gray, and Mr. White are fighting in a truel. They each get a gun and take turns shooting at each other until only one person is left. Mr. Black, who hits his shot 1/3 of the time, gets to shoot first. Mr. Gray, who hits his shot 2/3 of the time, gets to shoot next, assuming he is still alive. Mr. White, who hits his shot all the time, shoots next, assuming he is also alive. The cycle repeats. If you are Mr. Black, where should you shoot first for the highest chance of survival? * *Update Your Answers at* : Click Here http://dailybrainteaser.blogspot.com/2011/06/famous-probability-puzzle-shoot-8-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards DEVANSH GUPTA B.TECH SECOND 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse the bits.
@balaji: right , just one change required i think so coz in question they
are asking for change of one more bit i.e. for j=2,k=5.. bits 2,3,4,5 are
modified..ur code is doing i guess only 2,3,4.. i think just one change
needed int t2=(1(k+1))-1;
On Fri, Jun 10, 2011 at 10:22 PM, Vetri Balaji vetribal...@gmail.comwrote:
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.comwrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse the bits.
no..it will work just fine
On Sat, Jun 11, 2011 at 3:31 AM, Anika Jain anika.jai...@gmail.com wrote:
@balaji: right , just one change required i think so coz in question they
are asking for change of one more bit i.e. for j=2,k=5.. bits 2,3,4,5 are
modified..ur code is doing i guess only 2,3,4.. i think just one change
needed int t2=(1(k+1))-1;
On Fri, Jun 10, 2011 at 10:22 PM, Vetri Balaji vetribal...@gmail.comwrote:
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.comwrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
