Re: [algogeeks] (OOPS) Composition VS Inheritance
The problem with inheritence is that it is compile time(i.e a class A inheriting from class B cannot be modified again) whereas composition can be used to change the objects during runtime(by having a base class pointer we can change the objects runtime). Correct me if i'm wrong. On Sun, Jun 26, 2011 at 7:13 AM, HowTechStuffWorks howtechstuffwo...@gmail.com wrote: Why Composition is said to be good ahead of inheritance. I am just learning C++ and it was said inheritance can be handled only by expert programmers, but I dont see anything like that. Can some one give me an example. Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] [BRAIN TEASER]Popular Puzzle of the week
*Hi,* * * *Based on most comments, The popular puzzle of the last week is* * * * http://dailybrainteaser.blogspot.com/2011/06/find-next-number.html?lavesh=lavesh * * * ** * * * http://dailybrainteaser.blogspot.com/2011/06/sherlock-puzzle.html?lavesh=lavesh * * * You Can Also follow us on Facebook by liking this page *http://www.facebook.com/pages/Brain-Teasers/215057538517190* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] SPOJ STRDIST
http://www.spoj.pl/problems/STRDIST/
Getting WA repeatedly. Can someone help me with the below code.
#include iostream
#include string
#include stdio.h
#include algorithm
using namespace std;
int main()
{
int k,l;
scanf(%d %d,k,l);
string str1 = ;
string str2 = ;
if (k0)
cin str1;
if(l0)
cin str2;
str1 = 0 + str1;
str2 = 0 + str2;
int m,n;
m = k;
n = l;
int pos[][3] = {
{2,1,0},
{0,2,1},
{1,0,2}
};
int I,I1,I2;
int posIdx = 0;
int dp[3][n+1];
for (int i = 0 ; i 3; i++)
for (int j = 0 ; j =n; j++)
dp[i][j] = 200;
dp[0][0] = 0;
for (int i = 0 ; i = m; i++)
{
if (i = 2)
{
I = pos[posIdx][0]; I1 = pos[posIdx][1]; I2 =
pos[posIdx][2];
}
else
{
I=i;I1=i-1;
}
for (int j = 0 ; j =n; j++)
{
if (i == 0 j == 0) continue;
if ( j - i 105)
break;
bool updated = false;
if (j 0)
{
dp[I][j] = min(dp[I][j],dp[I][j-1] + 1);
updated = true;
}
if (i 0)
{
if (updated)
dp[I][j] = min(dp[I][j],dp[I1][j] + 1);
else
dp[I][j] = dp[I1][j] + 1;
}
if (i 0 j 0 str1[i] == str2[j])
{
dp[I][j] = min(dp[I][j],dp[I1][j-1]);
}
if (str1[i] == str2[j-1] str1[i-1] == str2[j]
i=2 j=2)
{
dp[I][j] = min(dp[I][j],dp[I2][j-2] + 1);
}
if (i 0 j 0 str1[i] != str2[j])
{
dp[I][j] = min(dp[I][j],dp[I1][j-1] + 1);
}
}
if (i = 2)
{
posIdx = (posIdx + 1)%3;
}
}
printf(%d\n,dp[k%3][l]);
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: Queue to support insert , delete, find max in o(1)
@Divye: Awesome solution dude with amortized complexity of O(1)! The examples made things even clearer :) On Jun 26, 8:13 am, DK divyekap...@gmail.com wrote: I've solved it for find_min() - the find_max implementations are analogous. Example: i = insert d = delete i 1 - q - 1 dq - 1 -- min value i 2 - q - 1 2 dq - 1 2 (min value = 1) d - q - 2 dq - 2 -- Note: min value changed i 0 - q - 2 0 dq - 0 -- Note: min value changed Hope this makes things even clearer. :) As for the bonus part. Let me know if you need an example. :) -- DK http://twitter.com/divyekapoorhttp://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Sorting Array
Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sorting Array
Yes ! Count Sort !! On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] [BRAIN TEASER]Popular Puzzle of the week
this is so helpful :P On Sun, Jun 26, 2011 at 12:30 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Hi,* * * *Based on most comments, The popular puzzle of the last week is* * * * http://dailybrainteaser.blogspot.com/2011/06/find-next-number.html?lavesh=lavesh * * * ** * * * http://dailybrainteaser.blogspot.com/2011/06/sherlock-puzzle.html?lavesh=lavesh * * * You Can Also follow us on Facebook by liking this page *http://www.facebook.com/pages/Brain-Teasers/215057538517190* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: strings
So finally what will be the solution? Harshal's solution doesn't print the characters in the order of appearance in the orignal array as nishant righly pointed out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: strings
anonymous see this http://ideone.com/TuNbS Can anyone tell me why gcc complier giving this warning prog.c:8: warning: implicit declaration of function ‘strlen’ On 6/26/11, anonymous procrastination opamp1...@gmail.com wrote: So finally what will be the solution? Harshal's solution doesn't print the characters in the order of appearance in the orignal array as nishant righly pointed out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: strings
use #includestring.h instead of #includestrings.h -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] image processing
I don't know how far u have been able to conquer the problem .. We tried this and used epipolar geometry and 7point algo and found the Homography matrix.. try referring to Hartley and Zeisserman book.!! On Thu, Jun 23, 2011 at 3:52 PM, DK divyekap...@gmail.com wrote: Perspective transformations are non linear because in this case Y = AX the matrix A is a function of Y and X. It would be linear only if A was independent of X and Y. (See the derivation on that link). -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/0IW6lE9KX60J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Sorting Array
@radhakrishnan: Counting sort in this case, will be O(n2).. as it involves traversing the entire array! On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote: Count sort is O(n+k), since k~n^2 here, it will be O(N^2). Radix sort has complexity O(r.n) which is nearly O(n logn). Are you sure that the person asking this question wanted O(n) ? On Jun 26, 1:31 pm, radha krishnan radhakrishnance...@gmail.com wrote: Yes ! Count Sort !! On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://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: Sorting Array
@L: It was asked if we could take advantage of the ranges of the integers between 1-N^2.. I doubt if its possible. On Jun 26, 5:33 pm, ross jagadish1...@gmail.com wrote: @radhakrishnan: Counting sort in this case, will be O(n2).. as it involves traversing the entire array! On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote: Count sort is O(n+k), since k~n^2 here, it will be O(N^2). Radix sort has complexity O(r.n) which is nearly O(n logn). Are you sure that the person asking this question wanted O(n) ? On Jun 26, 1:31 pm, radha krishnan radhakrishnance...@gmail.com wrote: Yes ! Count Sort !! On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://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: Sorting Array
@ross: I guess the orignal problem is that there are N numbers which are all in the range [1, N * N], can you do the sorting in O(N) time complexity? If this is true, we can firstly do the discretization and then do the counting sort. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Sorting Array
@Rujin Cao: Yea, your formulation of the problem is correct.. my bad,. missed that there are N numbers. can u elaborate more on the discretization procedure and how ll u do counting sort (which might warrant traversing of N^2 elements) On Jun 26, 5:45 pm, Rujin Cao drizzle...@gmail.com wrote: @ross: I guess the orignal problem is that there are N numbers which are all in the range [1, N * N], can you do the sorting in O(N) time complexity? If this is true, we can firstly do the discretization and then do the counting sort. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] image processing
hmm for starting this , we need 2 shots of a scene right? I have only a single image..no stereo vision here On Sun, Jun 26, 2011 at 2:16 PM, sukhmeet singh sukhmeet2...@gmail.comwrote: I don't know how far u have been able to conquer the problem .. We tried this and used epipolar geometry and 7point algo and found the Homography matrix.. try referring to Hartley and Zeisserman book.!! On Thu, Jun 23, 2011 at 3:52 PM, DK divyekap...@gmail.com wrote: Perspective transformations are non linear because in this case Y = AX the matrix A is a function of Y and X. It would be linear only if A was independent of X and Y. (See the derivation on that link). -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/0IW6lE9KX60J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Arun Vish Graduate Student Department of Computer Science University of Southern California -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: O(n) Time is the problem. ..
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came to know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com wrote:
@Sunny: What makes you think that the integers are 32 bits in length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n log
n) is correct for a naive algorithm. But a little thought can give a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)), where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can find it
as
following
ith bit of result = (xor of all ith bits of values of array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n except
for
one
number which is
missing. In this problem, we cannot access an entire integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and the
only
operation we can use
to access them is “fetch the jth bit of A[i]”, which takes
constant
time. Write code to
find the missing integer. Can you do it in O(n) time?
_
_ _
Rajeev N Bharshetty
I Blog @www.opensourcemania.co.cc
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To post
Re: [algogeeks] Re: O(n) Time is the problem. ..
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n log
n) is correct for a naive algorithm. But a little thought can give a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)), where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can find
it
as
following
ith bit of result = (xor of all ith bits of values of array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n
except
for
one
number which is
missing. In this problem, we cannot access an entire integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and the
only
operation we can use
to access them is “fetch the jth bit of A[i]”, which takes
constant
time. Write code to
find the missing integer. Can you do it in O(n) time?
_
_ _
Rajeev N Bharshetty
I Blog @www.opensourcemania.co.cc
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
Re: [algogeeks] Re: Sorting Array
@ross: It seems that after discretization , the time complexity still would be O(nlogn). The discretization idea is: say there are 4 numbers, each of them is in the range[1, 16]. e.g. 12 3 12 15 You can do one time transverse to map each of them to a global increasing index (hashing is the appropriate method) 12 --- 1 3 --- 2 15 --- 3 but we still need some data structure to hold the order of the numbers which is still O(nlogn). for this idea, using STL mapTkey, TValue would be much easier... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: O(n) Time is the problem. ..
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n log
n) is correct for a naive algorithm. But a little thought can give a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)), where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can find
it
as
following
ith bit of result = (xor of all ith bits of values of array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n
except
for
one
number which is
missing. In this problem, we cannot access an entire integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and the
only
operation we can use
to access them is “fetch the jth bit of A[i]”, which takes
constant
time. Write code to
find the missing integer. Can you do it in O(n) time?
_
_ _
Rajeev N Bharshetty
I Blog @www.opensourcemania.co.cc
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from 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: Sorting Array
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers.
Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
Assuming uniform distribution, the bins will have N/N ~ 1 element each.
If the distribution is non-uniform then no bin will have more than N
elements.
For small bins, apply a variant of insertion sort (which performs faster
than O(n log n) sorts for 12 elements) and if N is large, will perform
much faster than counting sort.
For large bins, apply an O(n log n) sort or radix sort or counting sort.
(make a choice depending on number of elements in the bin. eg. Num_elements
~ N then choose counting sort, else choose radix or O(n log n) sorts)
Complexity analysis:
1. No bin will have more than N elements.
2. No bin while being sorted will have a range N.
If the data distribution is uniform, the solution will be very very quick
(order of N) as the sorting time for bins with just 2 to 3 elements is
approximately O(num_elements) ~ O(1) and number of such bins is O(N).
If the data distribution is non-uniform, then complexity will depend on the
number of bad bins and the size of bad bins.
Let K bins be bad. Here, K is a value dependent on data distribution of the
input.
If K is small, number of elements per bin is large - apply counting sort on
the bins - complexity O(K N) which is approximately O(N)
If K - log N, apply an O(N log N) sort to the bins - complexity O( K * N/K
log (N/K)) - O(N log (N/log N))
If K log N but K N, worst case - complexity Sum over K bins{min{O(Ni
log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
sort)
If K - N - Not possible as you won't have that many bad bins as the number
of elements per bin will approach 1.
So, in short, you can get a complexity of the kind O(N log (N/log N)) which
is slightly better than O(N log N).
Hope this helps!
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
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/-/OCYjpn_zkigJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] image processing
YES.. we need to have 2 shots.. !! u said u had some matching points in the 2 images On Sun, Jun 26, 2011 at 6:23 PM, Arun Vishwanathan aaron.nar...@gmail.comwrote: hmm for starting this , we need 2 shots of a scene right? I have only a single image..no stereo vision here On Sun, Jun 26, 2011 at 2:16 PM, sukhmeet singh sukhmeet2...@gmail.comwrote: I don't know how far u have been able to conquer the problem .. We tried this and used epipolar geometry and 7point algo and found the Homography matrix.. try referring to Hartley and Zeisserman book.!! On Thu, Jun 23, 2011 at 3:52 PM, DK divyekap...@gmail.com wrote: Perspective transformations are non linear because in this case Y = AX the matrix A is a function of Y and X. It would be linear only if A was independent of X and Y. (See the derivation on that link). -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/0IW6lE9KX60J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Arun Vish Graduate Student Department of Computer Science University of Southern California -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Product of N numbers - with Constraints
Given an array A , of N integers ( In no particular order), fill up an auxilary array B such that B[i] contains the product of all elements in A other than A[i]. Constraints: O(n) Time, Can this be done with O(1) space? Division is *not* allowed . eg: A 1 2 3 4 5 B 120 60 40 30 24 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Sorting Array
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers.
Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
Assuming uniform distribution, the bins will have N/N ~ 1 element each.
If the distribution is non-uniform then no bin will have more than N
elements.
For small bins, apply a variant of insertion sort (which performs faster
than O(n log n) sorts for 12 elements) and if N is large, will perform
much faster than counting sort.
For large bins, apply an O(n log n) sort or radix sort or counting sort.
(make a choice depending on number of elements in the bin. eg. Num_elements
~ N then choose counting sort, else choose radix or O(n log n) sorts)
Complexity analysis:
1. No bin will have more than N elements.
2. No bin while being sorted will have a range N.
If the data distribution is uniform, the solution will be very very quick
(order of N) as the sorting time for bins with just 2 to 3 elements is
approximately O(num_elements) ~ O(1) and number of such bins is O(N).
If the data distribution is non-uniform, then complexity will depend on the
number of bad bins and the size of bad bins.
Let K bins be bad. Here, K is a value dependent on data distribution of the
input.
If K is small, number of elements per bin is large - apply counting sort on
the bins - complexity O(K N) which is approximately O(N)
If K - log N, apply an O(N log N) sort to the bins - complexity O( K * N/K
log (N/K)) - O(N log (N/log N))
If K log N but K N, worst case - complexity Sum over K bins{min{O(Ni
log (Ni)), O(N)}} (you can cheat this to O(N) by using something like radix
sort)
If K - N - Not possible as you won't have that many bad bins as the number
of elements per bin will approach 1.
So, in short, you can get a complexity of the kind O(N log (N/log N)) which
is slightly better than O(N log N).
Hope this helps!
--
DK
http://twitter.com/divyekapoorhttp://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Sorting Array
u can use radix sort
On Sun, Jun 26, 2011 at 9:44 PM, ross jagadish1...@gmail.com wrote:
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits
used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
Okay, since we don't want to cheat on this one, keep reading below: :)
Another method is to divide the Numbers into N bins of size N numbers.
Eg. Bin 1 = 1 to N, Bin 2 = N+1 to 2N ...
Assuming uniform distribution, the bins will have N/N ~ 1 element each.
If the distribution is non-uniform then no bin will have more than N
elements.
For small bins, apply a variant of insertion sort (which performs faster
than O(n log n) sorts for 12 elements) and if N is large, will perform
much faster than counting sort.
For large bins, apply an O(n log n) sort or radix sort or counting sort.
(make a choice depending on number of elements in the bin. eg.
Num_elements
~ N then choose counting sort, else choose radix or O(n log n) sorts)
Complexity analysis:
1. No bin will have more than N elements.
2. No bin while being sorted will have a range N.
If the data distribution is uniform, the solution will be very very quick
(order of N) as the sorting time for bins with just 2 to 3 elements is
approximately O(num_elements) ~ O(1) and number of such bins is O(N).
If the data distribution is non-uniform, then complexity will depend on
the
number of bad bins and the size of bad bins.
Let K bins be bad. Here, K is a value dependent on data distribution of
the
input.
If K is small, number of elements per bin is large - apply counting sort
on
the bins - complexity O(K N) which is approximately O(N)
If K - log N, apply an O(N log N) sort to the bins - complexity O( K *
N/K
log (N/K)) - O(N log (N/log N))
If K log N but K N, worst case - complexity Sum over K bins{min{O(Ni
log (Ni)), O(N)}} (you can cheat this to O(N) by using something like
radix
sort)
If K - N - Not possible as you won't have that many bad bins as the
number
of elements per bin will approach 1.
So, in short, you can get a complexity of the kind O(N log (N/log N))
which
is slightly better than O(N log N).
Hope this helps!
--
DK
http://twitter.com/divyekapoorhttp://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Product of N numbers - with Constraints
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Product of N numbers - with Constraints
#include iostream
using namespace std;
int main()
{
int input[10];
int n;
coutenter nendl;
cinn;
int output[10];
coutenter input arrayendl;
for(int i=0;in;i++)
cininput[i];
int a[n],b[n];
a[0]=1;
for(int i=1;in;i++)
{
a[i]=a[i-1]*input[i-1];
}
b[n-1]=1;
for(int i=n-2;i=0;i--)
{
b[i]=b[i+1]*input[i+1];
}
for(int i=0;in;i++)
{
output[i]=a[i]*b[i];
coutoutput[i]endl;
}
return 0;
}
On Sun, Jun 26, 2011 at 9:38 PM, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Product of N numbers - with Constraints
this is goog question
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Jun 26, 2011 at 10:04 PM, Dave dave_and_da...@juno.com wrote:
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: strings
this will need two passes first pass creates the hash map of char and count second pass walk over the the string again, refer hash map to print that many chars, remove this char from hash once printed and move on untill the complete string is covered or hashmap size is 0 Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jun 26, 2011 at 5:35 PM, Vikash kumar vikash.nitdgp9...@gmail.comwrote: use #includestring.h instead of #includestrings.h -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Product of N numbers - with Constraints
@Dave: Very good solution.. I had thought an idea of using separate
arrays to store next and previous products. And multiplying the
elements of the 2 arrays to give B. The solution given by you
satisfies ALL constraints inplace :)
@sameer: Your solution is not O(1) in space dude..Dave's solution is
good.
On Jun 26, 9:47 pm, Ashish Goel ashg...@gmail.com wrote:
this is goog question
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Jun 26, 2011 at 10:04 PM, Dave dave_and_da...@juno.com wrote:
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Anyone have The google resume book
-- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find solutions for Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example.
. Find solutions for Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example. Using Neural Networks with or without Genetic Algorithms to find solutions to Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey. Using the fish finding food HTML 5 and Javascript Neural Networks example http://www.nixuz.com:8080/html5/fish.html at as an example or template, replace the food particles the fish are hunting for as prey with solutions to the Clay Mathematics Institute Millennium Prize Problems as the prey. There is a million dollar prize for each problem solved. http://www.claymath.org/millennium/. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] puzzle
There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] puzzle
3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example.
Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example. . Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example. Using Neural Networks with or without Genetic Algorithms to find solutions to Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey. Using the fish finding food HTML 5 and Javascript Neural Networks example http://www.nixuz.com:8080/html5/fish.html at as an example or template, replace the food particles the fish are hunting for as prey with solutions to the Clay Mathematics Institute Millennium Prize Problems as the prey. There is a million dollar prize for each problem solved. http://www.claymath.org/millennium/. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Queue to support insert , delete, find max in o(1)
@DK - your solution works great but my only concern is that for the worst case, insert() is not really O(1). For example, if you have 1000 elements being inserted in ascending order and then 1001'st element is smaller than the first element, the insert() will become O(n). On Jun 25, 10:13 pm, DK divyekap...@gmail.com wrote: I've solved it for find_min() - the find_max implementations are analogous. Example: i = insert d = delete i 1 - q - 1 dq - 1 -- min value i 2 - q - 1 2 dq - 1 2 (min value = 1) d - q - 2 dq - 2 -- Note: min value changed i 0 - q - 2 0 dq - 0 -- Note: min value changed Hope this makes things even clearer. :) As for the bonus part. Let me know if you need an example. :) -- DK http://twitter.com/divyekapoorhttp://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: puzzle
can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Finding a number from 300million list with constraint on memory.
A small tweak (and possible optimization) to Dave's algorithm mighe be to use bit based array. That is, have an array of 12500 byte values where for each byte, the 8 bits represent a flag of whether that particular number is present in the file or not. So, a[0] would indicate whether numbers 1 - 10007 are present in the file or not. Now, we scan the file number by number, and for each number scanned, we convert the number into an index into the array and set the corresponding bit. After the entire file has been scanned, the task of finding a number not present in the file simply is to scan the array and find a bit which has not been set. To overcome the RAM limitation, we can keep 500KB of space for a chunk of the array which would be swapped in/out based on the values read from the file and the remaining 1.5MB would be used for the file contents. On Jun 23, 11:24 pm, Douglas Diniz dgdi...@gmail.com wrote: Well, I understood that you have a number (say x) and you want if the number x is not in the file. Atul wrote: The numbers are all distinct. they may vary from 100,000,000 to 999,999,999 and there are roughly 300 million (ie. 300 * 1000,000 numbers approx.). So there are 600*1000,000 number which are not in the file and we are asked to return any one these 600*1000,000 numbers given the memory constraints. Moreover the numbers are in random order. And in the first email: Find a 9-digit number that isn't present in the file. The description is ambiguous. But I think you are right. My interpretation was wrong. On Fri, Jun 24, 2011 at 1:06 AM, Dave dave_and_da...@juno.com wrote: @Douglas: I was assuming that the file contains the numbers in ASCII, and that normal file buffering is being used. If you think that I need to include the buffers in the given storage, then fine: just use half for buffers and half for the array of counters. The only change to the algorithm would be to replace 100 everywhere with 50. I find your description below a bit confusing, where you say that you will search for the number sequentially. What number are you searching for? The problem is to find a number that is not in the file, not to check to see if a given number is not in the file. Suppose that the file contains account numbers; the problem is to find an unused account number. So how do you search sequentially through a file to find a number that is not in the file? If I have misinterpreted what you wrote, please present your entire algorithm. Dave On Jun 23, 10:18 pm, Douglas Diniz dgdi...@gmail.com wrote: Dave, I think you method is very slow. If you have a array of 100 of 16 bits integers this mean that all the Ram is in use, and you will need at least 300x10^6 disk access, because you will need the read the numbers one by one from the file, and this will take a LOT of time. And your method use the module operation % for every number, which is slow. I think the basic algorithm of read blocks of 2MB to Ram and searching for the number sequentially until you find the number or reach the end of file, is some order of magnitude better, because you read the blocks linearly from the disk, which is much, much better than read one by one, and you dont have to calculate the %. On Thu, Jun 23, 2011 at 11:24 PM, Dave dave_and_da...@juno.com wrote: @Atul: Here is one way to do it: Treat the array as a million 16-bit integers: short a[100]. Set the array to zero. Read through the file, and for each number k, increment a[k%100]. Since the numbers are distinct, there can be at most 900 numbers in each bin. Find j such that a[j] 900. You now know that there is a missing number with the six-digit number j as the final six digits. Set a[100] to a[999] to zero. Read through the array again. Ignore any number k whose last six digits are not j. For the remaining numbers, set a[k/100] = 1. Find i, with 100 = i = 999, such that a[i]==0. This gives you the first three digits of a missing number. Put the first thee digits together with the last six digits: k = 100*i + j to get a number that is not in the file. Dave On Jun 23, 7:59 am, atul purohit gonewiththe...@gmail.com wrote: Hi, Can someone explain me how to do this. Given a file containing roughly 300 million 9-digit numbers. Find a 9-digit number that isn't present in the file.You have unlimited drive space but only 2MB of RAM available. I suppose we have to use bit-vectors n all but still couldnt figure out a proper way. A few steps or an algo will be great. Cheers, Atul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this
Re: [algogeeks] Re: puzzle
4 @amit what's the answer ? On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.comwrote: can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
3 think in binary.. :) On Mon, Jun 27, 2011 at 12:56 AM, Arpit Sood soodfi...@gmail.com wrote: 4 @amit what's the answer ? On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.comwrote: can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ankit Agarwal B.Tech. Senior Year Computer Science Engineering IIT Rajasthan *Be the change that you want to see in the world... :)* *- Gandhiji* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
first make two group of 3 bottle each one mice for each group make mixture of 3 bottle and put for mice . do same for other group only one mice will die . then select group of dead mice . beak it into three group one bottle each now we can use old mice which is not dead and one more for two bottle and which is going to die if no one then rest bottle out of three will be poisoned beer bottle On Mon, Jun 27, 2011 at 12:56 AM, Arpit Sood soodfi...@gmail.com wrote: 4 @amit what's the answer ? On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.comwrote: can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: puzzle
3 Mice: Call them mouse #1, mouse #2, and mouse #4 (think binary code). Give mouse #1 a mixture of bottles 1, 3, and 5. Give mouse #2 a mixture of bottles 2, 3, and 6. Give mouse #4 a mixture of bottles 4, 5, and 6. Add up the numbers of the mice that die to get the number of the poisoned beer bottle. Dave On Jun 26, 1:10 pm, amit the cool amitthecoo...@gmail.com wrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
you cant use the old mouse again because time he has mentioned is 14 hours... so you will have to wait for another 14 hours which exceeds the given time limit of 24 hours... so it is 4. On Mon, Jun 27, 2011 at 1:00 AM, D.N.Vishwakarma@IITR deok...@gmail.comwrote: first make two group of 3 bottle each one mice for each group make mixture of 3 bottle and put for mice . do same for other group only one mice will die . then select group of dead mice . beak it into three group one bottle each now we can use old mice which is not dead and one more for two bottle and which is going to die if no one then rest bottle out of three will be poisoned beer bottle On Mon, Jun 27, 2011 at 12:56 AM, Arpit Sood soodfi...@gmail.com wrote: 4 @amit what's the answer ? On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.com wrote: can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
thanks dave. On Mon, Jun 27, 2011 at 1:07 AM, Dave dave_and_da...@juno.com wrote: 3 Mice: Call them mouse #1, mouse #2, and mouse #4 (think binary code). Give mouse #1 a mixture of bottles 1, 3, and 5. Give mouse #2 a mixture of bottles 2, 3, and 6. Give mouse #4 a mixture of bottles 4, 5, and 6. Add up the numbers of the mice that die to get the number of the poisoned beer bottle. Dave On Jun 26, 1:10 pm, amit the cool amitthecoo...@gmail.com wrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: puzzle
@D.N.: The problem with your solution is that it can take up to 28 hours, but you must determine the poisoned beer in at most 24 hours. Dave On Jun 26, 2:30 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: first make two group of 3 bottle each one mice for each group make mixture of 3 bottle and put for mice . do same for other group only one mice will die . then select group of dead mice . beak it into three group one bottle each now we can use old mice which is not dead and one more for two bottle and which is going to die if no one then rest bottle out of three will be poisoned beer bottle On Mon, Jun 27, 2011 at 12:56 AM, Arpit Sood soodfi...@gmail.com wrote: 4 @amit what's the answer ? On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.comwrote: can u please explain how is it 3? On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote: 3 mice . On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.com wrote: 3 On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Arpit Bhatnagar (Computer Engineering) (MNIT JAIPUR) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Arpit Sood -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA * *- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding a number from 300million list with constraint on memory.
@Sankeet: How do you know that you wouldn't do more i/o for swapping than just reading the data twice? Since the input numbers are not sorted, it seems that you could be swapping a different block in for every number. Dave On Jun 26, 2:12 pm, Sanket vasa.san...@gmail.com wrote: A small tweak (and possible optimization) to Dave's algorithm mighe be to use bit based array. That is, have an array of 12500 byte values where for each byte, the 8 bits represent a flag of whether that particular number is present in the file or not. So, a[0] would indicate whether numbers 1 - 10007 are present in the file or not. Now, we scan the file number by number, and for each number scanned, we convert the number into an index into the array and set the corresponding bit. After the entire file has been scanned, the task of finding a number not present in the file simply is to scan the array and find a bit which has not been set. To overcome the RAM limitation, we can keep 500KB of space for a chunk of the array which would be swapped in/out based on the values read from the file and the remaining 1.5MB would be used for the file contents. On Jun 23, 11:24 pm, Douglas Diniz dgdi...@gmail.com wrote: Well, I understood that you have a number (say x) and you want if the number x is not in the file. Atul wrote: The numbers are all distinct. they may vary from 100,000,000 to 999,999,999 and there are roughly 300 million (ie. 300 * 1000,000 numbers approx.). So there are 600*1000,000 number which are not in the file and we are asked to return any one these 600*1000,000 numbers given the memory constraints. Moreover the numbers are in random order. And in the first email: Find a 9-digit number that isn't present in the file. The description is ambiguous. But I think you are right. My interpretation was wrong. On Fri, Jun 24, 2011 at 1:06 AM, Dave dave_and_da...@juno.com wrote: @Douglas: I was assuming that the file contains the numbers in ASCII, and that normal file buffering is being used. If you think that I need to include the buffers in the given storage, then fine: just use half for buffers and half for the array of counters. The only change to the algorithm would be to replace 100 everywhere with 50. I find your description below a bit confusing, where you say that you will search for the number sequentially. What number are you searching for? The problem is to find a number that is not in the file, not to check to see if a given number is not in the file. Suppose that the file contains account numbers; the problem is to find an unused account number. So how do you search sequentially through a file to find a number that is not in the file? If I have misinterpreted what you wrote, please present your entire algorithm. Dave On Jun 23, 10:18 pm, Douglas Diniz dgdi...@gmail.com wrote: Dave, I think you method is very slow. If you have a array of 100 of 16 bits integers this mean that all the Ram is in use, and you will need at least 300x10^6 disk access, because you will need the read the numbers one by one from the file, and this will take a LOT of time. And your method use the module operation % for every number, which is slow. I think the basic algorithm of read blocks of 2MB to Ram and searching for the number sequentially until you find the number or reach the end of file, is some order of magnitude better, because you read the blocks linearly from the disk, which is much, much better than read one by one, and you dont have to calculate the %. On Thu, Jun 23, 2011 at 11:24 PM, Dave dave_and_da...@juno.com wrote: @Atul: Here is one way to do it: Treat the array as a million 16-bit integers: short a[100]. Set the array to zero. Read through the file, and for each number k, increment a[k%100]. Since the numbers are distinct, there can be at most 900 numbers in each bin. Find j such that a[j] 900. You now know that there is a missing number with the six-digit number j as the final six digits. Set a[100] to a[999] to zero. Read through the array again. Ignore any number k whose last six digits are not j. For the remaining numbers, set a[k/100] = 1. Find i, with 100 = i = 999, such that a[i]==0. This gives you the first three digits of a missing number. Put the first thee digits together with the last six digits: k = 100*i + j to get a number that is not in the file. Dave On Jun 23, 7:59 am, atul purohit gonewiththe...@gmail.com wrote: Hi, Can someone explain me how to do this. Given a file containing roughly 300 million 9-digit numbers. Find a 9-digit number that isn't present in the file.You have unlimited drive space but only 2MB of RAM available. I suppose we have to use bit-vectors n all but still couldnt figure out a
[algogeeks] VAS
1. There are N address lines in the procesor, which is true regarding the virtual space of the running process and why a. there is no limit on virtual space b. 2^N bytes in virtual space c. it depends upon size of RAM d. none of the above -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
hw u r gettin 3 i m gettin 4 mine is make 4 grups 1,2,6 no 1 2,3,5 no 2 1,3,4 no 3 4,5,6no 4 nw out of 4 2 mice will die,and in their corresponding groups common bottle will give you the answer. correct me if i am wrong -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: puzzle
@Harshit: Check dave's solution... U'll get ur ans :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: puzzle
i got it :) nice @dev!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: NEED ALGO IN TIME 0.00
I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com wrote: http://www.spoj.pl/problems/FASHION/ i summit this question and my time is 0.02 as i used sorting and then multiply corresponding index value and sum them to get ans. but best time is 0.00 and 1.6M in C. can anyone tell me what is the best algo to solve this problem in 0.00 i.e. best algo * - - - - - WITH REGARDS, PRAMENDRA RATHI * ** *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.
[algogeeks] Re: Sorting Array
Your question is good for a classroom style discussion/debate. However, in the real world, there is no simple answer. There are lots of sorting algorithms. Each one has it's pros cons and no single sorting algorithm is best, especially when not much is known about the data to be sorted. In your case about all that we really know is that there are no negative numbers involved. I don't think that helps very much (any?). Then... you need to consider the programming language and computer system used for the implementation. Yes. They do matter. Sometimes, they matter a LOT.Don't assume that an O(x) algorithm is better than an O(y) algorithm just because x is less than y. Dan :-) On Jun 26, 12:14 am, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: O(n) Time is the problem. ..
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com
wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n
log
n) is correct for a naive algorithm. But a little thought can give
a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)),
where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can
find
it
as
following
ith bit of result = (xor of all ith bits of values of array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n
except
for
one
number which is
missing. In this problem, we cannot access an entire
integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and the
only
operation we can use
to access them is “fetch the jth bit of A[i]”, which takes
constant
time. Write code to
find the missing integer. Can you do it in O(n) time?
_
_ _
Rajeev N Bharshetty
I Blog @www.opensourcemania.co.cc
--
You received this message because you are subscribed to
the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from 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.
[algogeeks] Re: NEED ALGO IN TIME 0.00
@Dan: see, that is not the point. We are just looking for a better solution not just an algorithm which fetches us 0.00 time given the SPOJ conditions. Actually we are not worried about the compiler stuff because its all relative. Some other person on this SPOJ platform has submitted the code which runs in 0.00 sec so we want to think of the optimizations he might have employed which made his code to run faster. Another plus point is- the difference in the time might be covered by exploiting the SPOJ platform but in the meanwhile, we get to think, we might get a new approach to the problem or may be an inprovement in the algorithm being deployed. Thats the whole point. Its just relative. Someone has used some optimizations and got a better time so we are looking for it. People do write their functions to multiply, take modulus etc We skip the printf scanf calls instead switch to fread etc just to achieve the speedup. The purpose is not just to solve the problem but to solve it efficiently. Say we are just sorting an array, the way we do it, the memory we use etc. it all matters and SPOJ helps to measure the same relatively. The problem given might be trivial but the competition among thousands of coders trying to achieve the best time for the same builds the spirit and helps to explore new techniques, new algorithms. It all comes with an urge to make our code run faster. Regarding the 1.6M, I don't really kno what it means but if one is interested, you can look for it on the forums etc and you'll have your answer. Some addicted user must be knowing this stuff actually. At the end, its all about the competition after you discover the logic to solve the problem. When you don't have the urge to improve upon it, you won't discover something new, something efficient. These are my views. I am not an addicted SPOJ user. I might be mistaken but this is what i feel. Doom On Jun 26, 11:59 pm, Dan dant...@aol.com wrote: I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com wrote: http://www.spoj.pl/problems/FASHION/ i summit this question and my time is 0.02 as i used sorting and then multiply corresponding index value and sum them to get ans. but best time is 0.00 and 1.6M in C. can anyone tell me what is the best algo to solve this problem in 0.00 i.e. best algo * - - - - - WITH REGARDS, PRAMENDRA RATHI * ** *B.TECH 2ND YEAR* *COMPUTER SCIENCE AND ENGINEERING* *NIT ALLAHABAD*- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: O(n) Time is the problem. ..
Dave - Can you elaborate on how you can do this - you can determine
whether the low order bit of the missing number is 0 or 1
On Jun 26, 2:32 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com
wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n
log
n) is correct for a naive algorithm. But a little thought can give
a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)),
where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can
find
it
as
following
ith bit of result = (xor of all ith bits of values of array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n
except
for
one
number which is
missing. In this problem, we cannot access an entire
integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and the
only
operation we can use
to access them is “fetch the jth bit of A[i]”, which takes
constant
time. Write code to
find the missing integer. Can you do it in O(n) time?
_
_ _
Rajeev N Bharshetty
I Blog @www.opensourcemania.co.cc
--
You received this message because you are subscribed to
the
Google
Groups Algorithm Geeks group.
To post to this group, send email to
algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
[algogeeks] Re: puzzle
These type of solutions require to think in binary. First of all leave the last one because if we don't find a poisoned bottle in first 5 then it means the last one is poisoned. So 5 can be expressed using 3 bits. these 3 bits will correspond to mice... 1 indicates the mice drinks and 0 indicates it doesn't from the mentioned bottle. 1 - 001 2- 010 3- 011 4-100 5-101 the number on right is the bottle number for remaining five bottles. The binary number on right tells us which mouse drinks from which bottle. e.g. bottle no. 5 is taken by mice 1 and mice 3 whereas bottle no.3 is consumed by mice 2 and mice 3. Now after 14hrs, the mice which die will tell us which bottle was poisoned. Because the combination is unique. Doom On Jun 26, 11:10 pm, amit the cool amitthecoo...@gmail.com wrote: There are 6 beer bottle nd one is poisoned. we have mice who will die within 14 hrs after drinkin poisned beer. In 24 hrs we have to find poisoned beer bottle. How many no of mice we require to find out poisoned bottle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: strings
Harshal's solution can be modified to make it worth with just 1 pass over the input string. What we need is an additional link pointer for each entry in the auxillary array. Additionally, we need current and start pointers which will be null to start with. Now, for every character in the input string, we go to the particular index location in the array. If start == null, we make it point to the present array location. If count in array == 0 Set count = 1 If current == null Set current = present array location Else Set link property of the location pointed to by current = present array location Set current = present array location Else We increment the count If current != present array location and present array location's link != null Set link property of the location pointed to by current = present array location Set current = present array location Once the input string is parsed, we scan the array, starting at the location pointed by start and following the link pointers and printing the character as many times as the count present in the array. On Jun 26, 11:50 am, Ashish Goel ashg...@gmail.com wrote: this will need two passes first pass creates the hash map of char and count second pass walk over the the string again, refer hash map to print that many chars, remove this char from hash once printed and move on untill the complete string is covered or hashmap size is 0 Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jun 26, 2011 at 5:35 PM, Vikash kumar vikash.nitdgp9...@gmail.comwrote: use #includestring.h instead of #includestrings.h -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: puzzle
5 mice: result time complete bottle to mice1: 14 hour after 2.5 hour to mice2 : 16.5 hour after 2.5 hour to mice3 : 19 hour after 2.5 hour to mice4 : 21.5 hour after 2.5 hour to mice5 : 24 hour one of these 5 mice will die within 24 hour otherwise definitely 6th bottle is Poisson . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example.
Use the view as source code option in your web browser to view the code at http://www.nixuz.com:8080/html5/fish.html. Modify the code by replacing the food particle code with the Millennium or other problem code, save and run from your browser as a local file or upload to a host server / cloud as a web page. On Jun 27, 4:30 am, Ian Martin Ajzenszmidt iajzens...@gmail.com wrote: Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example. . Find solutions for Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey in HTML5 Javascript Neural Networks example. Using Neural Networks with or without Genetic Algorithms to find solutions to Clay Mathematics Institute Millennium Prize Problems by replacing the food particles as prey with the solutions as prey. Using the fish finding food HTML 5 and Javascript Neural Networks example http://www.nixuz.com:8080/html5/fish.html at as an example or template, replace the food particles the fish are hunting for as prey with solutions to the Clay Mathematics Institute Millennium Prize Problems as the prey. There is a million dollar prize for each problem solved.http://www.claymath.org/millennium/. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: O(n) Time is the problem. ..
@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the
last two bits of N need be considered, i.e., N 3. You could index
into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so
the expression can be evaluated with bit operations by (6 (N 3))
1. Also, calculate the xor of the low order bits of the data. If the
two quantities agree, you know that the low order bit of the missing
data is 0, else it is 1.
Dave
On Jun 26, 5:23 pm, Sanket vasa.san...@gmail.com wrote:
Dave - Can you elaborate on how you can do this - you can determine
whether the low order bit of the missing number is 0 or 1
On Jun 26, 2:32 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just came
to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com wrote:
@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com
wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus, O(n
log
n) is correct for a naive algorithm. But a little thought can
give
a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com
wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32 depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)),
where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can
find
it
as
following
ith bit of result = (xor of all ith bits of values of
array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n] contains all the integers from 0 to n
except
for
one
number which is
missing. In this problem, we cannot access an entire
integer
in
A
with
a single opera-
tion. The elements of A are represented in binary, and
the
only
operation we can use
to access them is “fetch the jth
[algogeeks] Re: O(n) Time is the problem. ..
Thanks Dave.
Won't Also, calculate the xor of the low order bits of the data
require you to access each value in the array once? Or am I not
understanding what you meant?
On Jun 26, 6:50 pm, Dave dave_and_da...@juno.com wrote:
@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the
last two bits of N need be considered, i.e., N 3. You could index
into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so
the expression can be evaluated with bit operations by (6 (N 3))
1. Also, calculate the xor of the low order bits of the data. If the
two quantities agree, you know that the low order bit of the missing
data is 0, else it is 1.
Dave
On Jun 26, 5:23 pm, Sanket vasa.san...@gmail.com wrote:
Dave - Can you elaborate on how you can do this - you can determine
whether the low order bit of the missing number is 0 or 1
On Jun 26, 2:32 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not
acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just
came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com
wrote:
@Sunny. You are reading too much into that. There is no mention
that
the data are 32-bit integers. Perhaps they are big integers. What
we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave it is given in Question that elements of array are integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com
wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus,
O(n
log
n) is correct for a naive algorithm. But a little thought can
give
a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com
wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32
depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)),
where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can
find
it
as
following
ith bit of result = (xor of all ith bits of values of
array)
xored
with
(ith
bit of temp)
On Thu, Jun 23, 2011 at 12:25 AM, oppilas .
jatka.oppimi...@gmail.comwrote:
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack
rajeevr...@gmail.com
wrote:
An array A[1...n]
Re: [algogeeks] Re: Product of N numbers - with Constraints
http://anandtechblog.blogspot.com/2010/09/given-array-of-numbers-replace-each.html
On Sun, Jun 26, 2011 at 10:12 AM, ross jagadish1...@gmail.com wrote:
@Dave: Very good solution.. I had thought an idea of using separate
arrays to store next and previous products. And multiplying the
elements of the 2 arrays to give B. The solution given by you
satisfies ALL constraints inplace :)
@sameer: Your solution is not O(1) in space dude..Dave's solution is
good.
On Jun 26, 9:47 pm, Ashish Goel ashg...@gmail.com wrote:
this is goog question
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Jun 26, 2011 at 10:04 PM, Dave dave_and_da...@juno.com wrote:
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular order), fill up
an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: (OOPS) Composition VS Inheritance
@HowTechStuffWorks - I haven't heard of a recommendation to use composition over inheritance. In my opinion, it is simply based on the problem space. If you have related entities that have commonality that you wish to abstract, you use inheritance. Composition is preferred when you have dependent entities where the existence/meaningfulness of a dependent entity exists only in the context of it's containing entity. @pacific - I would tend to disagree with your reason. Composition structure also is determined at compile time itself. For example, class A contains a reference to an object of class B. Also, base class means you are using inheritance so when you say composition can be used to change the objects during runtime(by having a base class pointer we can change the objects runtime) it is not entirely accurate. On Jun 26, 1:39 am, pacific :-) pacific4...@gmail.com wrote: The problem with inheritence is that it is compile time(i.e a class A inheriting from class B cannot be modified again) whereas composition can be used to change the objects during runtime(by having a base class pointer we can change the objects runtime). Correct me if i'm wrong. On Sun, Jun 26, 2011 at 7:13 AM, HowTechStuffWorks howtechstuffwo...@gmail.com wrote: Why Composition is said to be good ahead of inheritance. I am just learning C++ and it was said inheritance can be handled only by expert programmers, but I dont see anything like that. Can some one give me an example. Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
hey harry.what r u upto? guys have already shown that answer is three On Mon, Jun 27, 2011 at 4:45 AM, hary rathor harry.rat...@gmail.com wrote: 5 mice: result time complete bottle to mice1: 14 hour after 2.5 hour to mice2 : 16.5 hour after 2.5 hour to mice3 : 19 hour after 2.5 hour to mice4 : 21.5 hour after 2.5 hour to mice5 : 24 hour one of these 5 mice will die within 24 hour otherwise definitely 6th bottle is Poisson . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Nagarro Question
Need a Better Algorithm
here is a trivial question we are given an array of 2n elements in the
form
{a1,a2,a3,..,an,b1,b2,b3b...bn}
we need to output a resultiing array in the form
{a1,b1,a2,b2,an,bn}
but without using another array here is my algorithm which uses nested
loops can anyone provide a better solution which doesnt involve
shifting.
int i,j,k,temp;
j=num;
int Interleave(int *arr)
{
for(i=1;i2*num - 1;i+=2)
{
temp = arr[j];
for(k=j;k=i+1;--k)
arr[k]=arr[k-1];
arr[i] = temp;
++j;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: NEED ALGO IN TIME 0.00
You are correct, this question is by no means testing anything non trivial/hard. It is one of the problems that the beginners in competitive programming solve. As for the discussion regarding this problem in current thread, some enthusiastic guy had got this AC in 0.08 at SPOJ, and everyone was trying to see how to implement the program efficiently to get it down to 0.00 Seconds. Thanks, Rizwan. On Mon, Jun 27, 2011 at 12:29 AM, Dan dant...@aol.com wrote: I found the problem statement on the web page link to be a bit weak. Nothing in the problem statement says that you must do anything other than read in two lines of integers and multiply them in pairs and sum the results ( ie. Dot Product ). People seem to think that you should sort the data first ( an assumption that is NOT in the problem statement ). Does that mean that you get the problem wrong if you don't sort the data first? Also... it looks as if you have to write the code in one of the listed languages. Is that true? You then submit your text code and it is compiled somewhere else? What compiler(s) is/are used and with what settings? This can affect both speed and memory (by large amounts). Also... exactly what does 1.6M for memory mean? For the moment, let's assume that you ARE supposed to sort the data first. Then... at best, all this test really does is check to see if you can read and sort data quickly. Multiplying pairs of numbers is trivial and I doubt many individuals are writing much code to speed up this simple Dot Product calculation. So... unless you write your own integer sorting algorithm that you are very proud of, what's the point of this test (other than it might be worthwhile as a homework assignment to new coders). Have I missed something? Dan :-) On Jun 24, 9:53 am, prathimzn prathi...@gmail.com wrote: http://www.spoj.pl/problems/FASHION/ i summit this question and my time is 0.02 as i used sorting and then multiply corresponding index value and sum them to get ans. but best time is 0.00 and 1.6M in C. can anyone tell me what is the best algo to solve this problem in 0.00 i.e. best algo * - - - - - WITH REGARDS, PRAMENDRA RATHI * ** *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 and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: NEED ALGO IN TIME 0.00
I am able to get this accepted with 0.00 Seconds http://ideone.com/Eg2wZ But, I am using 512 KB Buffer. Not sure how I do get 0.00 with a smaller buffer size say 8KB On Sun, Jun 26, 2011 at 7:54 AM, Wladimir Tavares wladimir...@gmail.com wrote: sometimes using global static variables may be better to use dynamic variables on the stack! Sometimes! Wladimir Araujo Tavares Federal University of Ceará On Sat, Jun 25, 2011 at 7:32 PM, Dumanshu duman...@gmail.com wrote: finally got it in 0.01 sec using all the optimizations i am aware of including what Wladimir had suggested. Now wat to do for 0.00??? heres my code- http://ideone.com/lsK8n please suggest if any further optimizations possible. On Jun 26, 2:21 am, Dumanshu duman...@gmail.com wrote: Ok, it seems like bucket sort is the best way to do it. I got 0.06 and to go further we need to use char buffer like the one Wladimir suggested. But still i have a doubt that would it be possible to reduce 0.06 to 0.00 using that buffer? I don't think there can be any possible improvement in logic. wat do u think? On Jun 26, 12:25 am, Dumanshu duman...@gmail.com wrote: see i got 0.07 sec as the time after using counting sort.. because the hotness scale is 0-10 so i used an array of 11 ints to count the no. of occurrences. But i m nt able to further reduce this. ny suggestions? theres a comment on the problem: On an interesting side note: the maximising principle underlying this problem generalises to almost-everywhere finite functions on sigma- finite measure spaces by a theorem of Hardy and Littlewood, see Theorem II.2.2 in C. Bennett, R. Sharpley, Interpolation of Operators ny use??? On Jun 25, 3:08 pm, prathimzn prathi...@gmail.com wrote: somebody answer how to reduce time *- - - - - WITH REGARDS, * * PRAMENDRA RATHI * ** *B.TECH 2ND YEAR* *COMPUTER SCIENCE AND ENGINEERING* *NIT ALLAHABAD* On Sat, Jun 25, 2011 at 12:27 AM, prathimzn prathi...@gmail.com wrote: sorry my time is 0.2 and i use simple int array and sort function of algorithm... *- - - - - WITH REGARDS, * * PRAMENDRA RATHI * ** *B.TECH 2ND YEAR* *COMPUTER SCIENCE AND ENGINEERING* *NIT ALLAHABAD* On Sat, Jun 25, 2011 at 12:04 AM, sunny agrawal sunny816.i...@gmail.comwrote: i am not sure about this but when i solved this problem using simple scanf, printf and sort function of algorithm library, my time was 0.08 so might be reading the values in character buffer and then parsing then in ints may help how did you implemented ? did you implemented your own sort funtion ? which input/output methods you used ? On Fri, Jun 24, 2011 at 11:23 PM, prathimzn prathi...@gmail.com wrote: http://www.spoj.pl/problems/FASHION/ i summit this question and my time is 0.02 as i used sorting and then multiply corresponding index value and sum them to get ans. but best time is 0.00 and 1.6M in C. can anyone tell me what is the best algo to solve this problem in 0.00 i.e. best algo * - - - - - WITH REGARDS, PRAMENDRA RATHI * ** *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. -- 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: O(n) Time is the problem. ..
@Sanket: Yes. That is the first O(n) in my previous posting
http://groups.google.com/group/algogeeks/msg/cd32a2276c6a2d22.
Dave
On Jun 26, 6:55 pm, Sanket vasa.san...@gmail.com wrote:
Thanks Dave.
Won't Also, calculate the xor of the low order bits of the data
require you to access each value in the array once? Or am I not
understanding what you meant?
On Jun 26, 6:50 pm, Dave dave_and_da...@juno.com wrote:
@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the
last two bits of N need be considered, i.e., N 3. You could index
into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so
the expression can be evaluated with bit operations by (6 (N 3))
1. Also, calculate the xor of the low order bits of the data. If the
two quantities agree, you know that the low order bit of the missing
data is 0, else it is 1.
Dave
On Jun 26, 5:23 pm, Sanket vasa.san...@gmail.com wrote:
Dave - Can you elaborate on how you can do this - you can determine
whether the low order bit of the missing number is 0 or 1
On Jun 26, 2:32 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On Jun 26, 2:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do
not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
generally when we talk about integers, they are 32 bit integers in
Programing/Algorithm Questions
so i was assuming that here
and about my solution - yes it will be O(nlgn) or O(nw) not
acceptable
for
given Q :(
and yes a Divide and Conquer solution can do it in O(n). I just
came to
know
..thanks
i little bit similer to my approachNice One
On Sat, Jun 25, 2011 at 9:15 PM, Dave dave_and_da...@juno.com
wrote:
@Sunny. You are reading too much into that. There is no mention
that
the data are 32-bit integers. Perhaps they are big integers.
What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal sunny816.i...@gmail.com
wrote:
@Dave it is given in Question that elements of array are
integer
On Sat, Jun 25, 2011 at 7:17 AM, Dave dave_and_da...@juno.com
wrote:
@Sunny: What makes you think that the integers are 32 bits in
length.
Remember that O(.) notation applies as n -- infinity. Thus,
O(n
log
n) is correct for a naive algorithm. But a little thought
can give
a
divide-and-conquer algorithm which is O(n).
Dave
On Jun 24, 8:44 am, sunny agrawal sunny816.i...@gmail.com
wrote:
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn = 32
depending
upon
value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda
rizwanhu...@gmail.com
wrote:
@sunny: Think again, your solution will take O(n*log(n)),
where
log(n)
is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan
2448...@gmail.com
wrote:
can you explain mewhat the logic is...behind the xor
operation?...is
it like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
initially compute xor of all the values from 0 to n in
a
variable
Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we
can
find
it
as
following
ith bit of result = (xor of all ith bits of values of
array)
xored
with
(ith
bit of temp)
Re: [algogeeks] VAS
2^N bytes in virtual space. Because since the processor has N address lines so the processor can address only 2^N bytes of data, even though the actual RAM may be less than 2^N bytes of data or the RAM allocated to a process is less than that. On Sun, Jun 26, 2011 at 12:49 PM, Akshata Sharma akshatasharm...@gmail.com wrote: 1. There are N address lines in the procesor, which is true regarding the virtual space of the running process and why a. there is no limit on virtual space b. 2^N bytes in virtual space c. it depends upon size of RAM d. none of the above -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
