"That number wont ever change. Regardless if you have 2 numbers or
257 numbers in your array. If you scale that to 32 bit numbers, you
get the following requirement ~ 135,000,000 distinct integers. It is a
large requirement, but it is constant and capable of determining what
you want regardless if it has 2 or 4,294,967,297 elements. "
so, does 135,000,000 distinct integers work for any size of input?
(Nowhere in the original problem did it say we were 1. working with 32
bit numbers, or, for that matter, 2. working with a bounded set --
where did the initial problem say anything about there being a maximum
value -- this is a theoretical question) Whenever you are working with
problems like this -- if you are going to put bounds on the set of
numbers you are using, you state that you are working in a RAM (or
even a Real RAM) model of computation, 32 bits (for instance). In the
absence of any such declaration, the assumption must be that you are
in the Comparison Model of computation, and the numbers are infinite
(after all, as an asymptotic exercise, who said that this problem was
ever to be coded...)
No. 135,000,000 integers do not work for any size of the input (in the
number of the array, or in representing any element of the array). It
grows as a function of the input size, thus as a function, it is not
constant... And it is not a valid solution for the problem as stated.
Your solution really parses terms on what it means to be performing
asymptotic analysis... you cannot say that this storage is constant in
32 bits, when it is not said that you are using 32 bit numbers. If you
are speaking asymptotically at all, saying that something is O(n) or
O(log(n)) or anything else then _by definition_ you are talking about
infinity...
On Aug 24, 11:19 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 10:19 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
>
> > > Sorry. I wrote too quickly. The amount you need is not determined by
> > > log, but by division.
> > > For the sake of argument, say you could hold the value 0 - 255. This
> > > means we are dealing with 8-bit storage, but it makes the example
> > > easier. You would need, 255/8 or roughly 32 distinct integers to do
> > > it.
>
> > How is what you are describing here not logarithmic storage? If the
> > number you need to use to encode your solution grows with the number
> > of bits needed to represent an piece of data involved, then your
> > solution is using log space...
>
> Not exactly logarithmic, but the point is, that there is a maximum
Maybe it is not growing logarithmically, but it is growing as a
function.... noone ever said we were working with anything other than
unbounded integers....
> value that teh array can have, regardless of the number of elements
> actually in it. The size of an integer value (in bits or otherwise) is
> fixed for any one array, and that, in turn, fixes the space you need
> to represent it. You are confusing the size fo the array (on which
> space and time complexity are based) with the size of the storage unit
> of an integer. The two ore disjoint.
>
>
>
> > That number wont ever change. Regardless if you have 2 numbers or
>
> > > 257 numbers in your array. If you scale that to 32 bit numbers, you
> > > get the following requirement ~ 135,000,000 distinct integers. It is a
> > > large requirement, but it is constant and capable of determining what
> > > you want regardless if it has 2 or 4,294,967,297 elements.
>
> > > Now, if you want to minimize that storage, you can scan the array
> > > first and pick out the maximum of the array. That is an O(n)
> > > operation. Base your static 'hash' on that maximum and you use the
> > > smallest amount of space. Realize that O(n) + O(n) results in O(n).
>
> > > On Aug 21, 1:08 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > Sorry, my own calculations are wrong - 7 32-bit integers can only
> > > > represent 32 * 7 bits of information,
> > > > I mistakenly added the redundant term '8' in the previous post. But
> > > > the idea is the same - 32 * 7 bits of information
> > > > cannot hold presence indicators for 2^32 numbers.
>
> > > > On Aug 21, 9:06 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > Let's count: log base 32 of the max value of an integer, or, rather,
> > > > > total amount of integers which can be stored in 32 bits (=2^32), is
> > > > > equal to
> > > > > ceil(log_32(2^32)) = 7. But 7 32-bit integers can only represent 32 *
> > > > > 7 * 8 bits of information
> > > > > which is not enough to store membership information for arbitrary
> > > > > numbers in range [1...2^32]. Sorry if I've again
> > > > > missed something in your proposal...
>
> > > > > On Aug 21, 6:14 am, L7 <[EMAIL PROTECTED]> wrote:
>
> > > > > > On Aug 20, 3:10 pm, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > > > Sorry, it's too late here, so I'm not sure I've completely
> > > > > > > understood
> > > > > > > the solution... Am I right that what is proposed
> > > > > > > is to create a huge bit vector of size (if I'm not wrong) 2^32
> > > > > > > bits
>
> > > > > > Not exactly. You can store 32 unique indicies in a 32-bit integer.
> > > > > > So
> > > > > > basically you need log base 32 of the max value of an integer.
>
> > > > > > > (assuming 32-bit integers) and use the value of an element array
> > > > > > > as an
> > > > > > > index to this vector? Then a linear algorithm solving the original
> > > > > > > problem is indeed not hard to figure out... The only problem is
> > > > > > > that
> > > > > > > I'm not sure if the array of size of 2^32 / 8 bytes can be
> > > > > > > considered
> > > > > > > a constant memory...
>
> > > > > > If you only speak of 32-bits (or 64, whichever the case) then you
> > > > > > will
> > > > > > never have to resize the array at any time. Indeed, you will have a
> > > > > > large amount of unused space (for smaller arrays) - but the size
> > > > > > does
> > > > > > not change with the size of the array and therefore can be
> > > > > > considered
> > > > > > constant.
>
> > > > > > > On Aug 20, 1:10 am, L7 <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > This can be done with constant space and O(n) time if you hold
> > > > > > > > to
> > > > > > > > _exactly_ what is mentioned in your post. An integer (32/64)
> > > > > > > > can hold
> > > > > > > > only a finite number of values. Based on that, you can create a
> > > > > > > > bitfield at size log of that mamimum value. You now have
> > > > > > > > constant size
> > > > > > > > 'hashing' where the hash is simply 1 << x[n]. Now the hash is
> > > > > > > > not a
> > > > > > > > problem of growth based on the size of the array. With that
> > > > > > > > implementation of sumedh sakdeo's hash solution you have the
> > > > > > > > problem
> > > > > > > > solved.
>
> > > > > > > > On Aug 19, 1:45 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > Hello,
>
> > > > > > > > > as I already mentioned, there are no any additional
> > > > > > > > > constraints on the
> > > > > > > > > input data, so you cannot assume
> > > > > > > > > that the array is ordered. Nor can you order it, as I presume
> > > > > > > > > that the
> > > > > > > > > input data should remain intact (sorry, I must have mentioned
> > > > > > > > > this
> > > > > > > > > before). So a solution cannot be based upon the assumption
> > > > > > > > > you made.
>
> > > > > > > > > Thanks.
>
> > > > > > > > > On Aug 18, 2:14 pm, "Peeyush Bishnoi" <[EMAIL PROTECTED]>
> > > > > > > > > wrote:
>
> > > > > > > > > > Hello All
> > > > > > > > > > I thanxs Vaibhav to give feedback on my solution....
>
> > > > > > > > > > I am once again putting my solution back on this group. I
> > > > > > > > > > welcome ur all
> > > > > > > > > > valuale feedback on this...
> > > > > > > > > > I can think this solution will work with constant space &
> > > > > > > > > > linear time ....
> > > > > > > > > > incomparison to my previous solution which is n*n at worst
> > > > > > > > > > case.
> > > > > > > > > > But this solution need integer array data set to be
> > > > > > > > > > sorted...
>
> > > > > > > > > > int main(){
> > > > > > > > > > int a[]={1,2,2,3};
> > > > > > > > > > int count=sizeof(a)/sizeof(a[0]);
> > > > > > > > > > printf("No.of elemenst:%d\n",count);
> > > > > > > > > > fun(a,count);
> > > > > > > > > > return 0;
>
> > > > > > > > > > }
>
> > > > > > > > > > fun(int a[],int count){
> > > > > > > > > > int i,j;
> > > > > > > > > > for(i=0,j=i+1;i<count,(i<j &&
> > > > > > > > > > (a[i]!=a[j]));i++,j++);
> > > > > > > > > > if((i<j)&& (a[i]==a[j])){
> > > > > > > > > > printf("No. is
> > > > > > > > > > repeated:%d\n",a[i]);
> > > > > > > > > > }else{
>
> > > > > > > > > > }
>
> > > > > > > > > > }
>
> > > > > > > > > > ---
> > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > On 8/18/07, Vaibhav Jain <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > peeyush,
>
> > > > > > > > > > > take eg: n=6
> > > > > > > > > > > array values: 10 20 30 40 50 50
> > > > > > > > > > > in worst case, while loop which can increment 'i' can go
> > > > > > > > > > > upto n-1
> > > > > > > > > > > and for loop (for 'j') every n-1 time check upto n times
> > > > > > > > > > > so total it becomes (n-1)*n= O(n*n).
>
> > > > > > > > > > > like this i think u can observe now..
>
> > > > > > > > > > > On 8/18/07, Peeyush Bishnoi <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > > Thanxs for giving feedback... :-)
> > > > > > > > > > > > Can you please explain how worst case time complexity
> > > > > > > > > > > > is O(n*n) of
> > > > > > > > > > > > this solution. Means how u determine this. Plz
> > > > > > > > > > > > explain....
>
> > > > > > > > > > > > ---
> > > > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > > > On 8/18/07, Vaibhav Jain <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > > > hi peeyush,
>
> > > > > > > > > > > > > ur solution is nice, it is brute force method and
> > > > > > > > > > > > > space complexity is
> > > > > > > > > > > > > constant here
> > > > > > > > > > > > > but ur solution contains worst case time complexity
> > > > > > > > > > > > > O(n*n)
> > > > > > > > > > > > > and we want O(n) solution. So ur solution is not
> > > > > > > > > > > > > required solution.
>
> > > > > > > > > > > > > On 8/18/07, Peeyush Bishnoi < [EMAIL PROTECTED]>
> > > > > > > > > > > > > wrote:
>
> > > > > > > > > > > > > > Hello All ,
>
> > > > > > > > > > > > > > I am thinking this solution offered by me is some
> > > > > > > > > > > > > > what accurate with
> > > > > > > > > > > > > > constant space . Just put ur feed back on this.
>
> > > > > > > > > > > > > > If you have any query ask me.
>
> > > > > > > > > > > > > > int main(){
> > > > > > > > > > > > > > int a[]={1,2,2,3};
> > > > > > > > > > > > > > int count=sizeof(a)/sizeof(a[0]);
> > > > > > > > > > > > > > printf("No.of elemenst:%d\n",count);
> > > > > > > > > > > > > > fun(a,count);
> > > > > > > > > > > > > > return 0;
> > > > > > > > > > > > > > }
>
> > > > > > > > > > > > > > fun(int a[],int count){
> > > > > > > > > > > > > > int i=0,j;
> > > > > > > > > > > > > > while(i<count){
> > > > > > > > > > > > > > for(j=0;(j<i && (a[i]!=a[j]));j++);
> > > > > > > > > > > > > > if((j<i)&& (a[i]==a[j])){
> > > > > > > > > > > > > > printf("No. is
> > > > > > > > > > > > > > repeated:%d\n",a[i]);
> > > > > > > > > > > > > > }else{
> > > > > > > > > > > > > > }
> > > > > > > > > > > > > > i++;
> > > > > > > > > > > > > > }
> > > > > > > > > > > > > > }
>
> > > > > > > > > > > > > > ---
> > > > > > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > > > > > On 8/18/07, Dondi Imperial < [EMAIL PROTECTED] >
> > > > > > > > > > > > > > wrote:
>
> > > > > > > > > > > > > > > hi,
>
> > > > > > > > > > > > > > > actually in mine space complexity is O(n) in
> > > > > > > > > > > > > > > _all_ cases. :). Out
> > > > > > > > > > > > > > > of
> > > > > > > > > > > > > > > curiousity, will your solution work when not all
> > > > > > > > > > > > > > > the numbers in
> > > > > > > > > > > > > > > the
> > > > > > > > > > > > > > > range are present in the array?
>
> > > > > > > > > > > > > > > Thanks,
>
> > > > > > > > > > > > > > > Dondi
>
> > > > > > > > > > > > > > > On 8/17/07, Vaibhav Jain < [EMAIL PROTECTED] >
> > > > > > > > > > > > > > > wrote:
> > > > > > > > > > > > > > > > hello Dondi,
>
> > > > > > > > > > > > > > > > in ur solution, space complexity will be O(n)
> > > > > > > > > > > > > > > > in worst case.
> > > > > > > > > > > > > > > > but in my solution it will constant space with
> > > > > > > > > > > > > > > > linear
> > > > > > > > > > > > > > > complexity.
>
> > > > > > > > > > > > > > > > now think abt how to prove it if range is not
>
> ...
>
> read more >>
On Aug 24, 11:19 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 10:19 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
>
> > > Sorry. I wrote too quickly. The amount you need is not determined by
> > > log, but by division.
> > > For the sake of argument, say you could hold the value 0 - 255. This
> > > means we are dealing with 8-bit storage, but it makes the example
> > > easier. You would need, 255/8 or roughly 32 distinct integers to do
> > > it.
>
> > How is what you are describing here not logarithmic storage? If the
> > number you need to use to encode your solution grows with the number
> > of bits needed to represent an piece of data involved, then your
> > solution is using log space...
>
> Not exactly logarithmic, but the point is, that there is a maximum
> value that teh array can have, regardless of the number of elements
> actually in it. The size of an integer value (in bits or otherwise) is
> fixed for any one array, and that, in turn, fixes the space you need
> to represent it. You are confusing the size fo the array (on which
> space and time complexity are based) with the size of the storage unit
> of an integer. The two ore disjoint.
>
>
>
> > That number wont ever change. Regardless if you have 2 numbers or
>
> > > 257 numbers in your array. If you scale that to 32 bit numbers, you
> > > get the following requirement ~ 135,000,000 distinct integers. It is a
> > > large requirement, but it is constant and capable of determining what
> > > you want regardless if it has 2 or 4,294,967,297 elements.
>
> > > Now, if you want to minimize that storage, you can scan the array
> > > first and pick out the maximum of the array. That is an O(n)
> > > operation. Base your static 'hash' on that maximum and you use the
> > > smallest amount of space. Realize that O(n) + O(n) results in O(n).
>
> > > On Aug 21, 1:08 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > Sorry, my own calculations are wrong - 7 32-bit integers can only
> > > > represent 32 * 7 bits of information,
> > > > I mistakenly added the redundant term '8' in the previous post. But
> > > > the idea is the same - 32 * 7 bits of information
> > > > cannot hold presence indicators for 2^32 numbers.
>
> > > > On Aug 21, 9:06 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > Let's count: log base 32 of the max value of an integer, or, rather,
> > > > > total amount of integers which can be stored in 32 bits (=2^32), is
> > > > > equal to
> > > > > ceil(log_32(2^32)) = 7. But 7 32-bit integers can only represent 32 *
> > > > > 7 * 8 bits of information
> > > > > which is not enough to store membership information for arbitrary
> > > > > numbers in range [1...2^32]. Sorry if I've again
> > > > > missed something in your proposal...
>
> > > > > On Aug 21, 6:14 am, L7 <[EMAIL PROTECTED]> wrote:
>
> > > > > > On Aug 20, 3:10 pm, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > > > Sorry, it's too late here, so I'm not sure I've completely
> > > > > > > understood
> > > > > > > the solution... Am I right that what is proposed
> > > > > > > is to create a huge bit vector of size (if I'm not wrong) 2^32
> > > > > > > bits
>
> > > > > > Not exactly. You can store 32 unique indicies in a 32-bit integer.
> > > > > > So
> > > > > > basically you need log base 32 of the max value of an integer.
>
> > > > > > > (assuming 32-bit integers) and use the value of an element array
> > > > > > > as an
> > > > > > > index to this vector? Then a linear algorithm solving the original
> > > > > > > problem is indeed not hard to figure out... The only problem is
> > > > > > > that
> > > > > > > I'm not sure if the array of size of 2^32 / 8 bytes can be
> > > > > > > considered
> > > > > > > a constant memory...
>
> > > > > > If you only speak of 32-bits (or 64, whichever the case) then you
> > > > > > will
> > > > > > never have to resize the array at any time. Indeed, you will have a
> > > > > > large amount of unused space (for smaller arrays) - but the size
> > > > > > does
> > > > > > not change with the size of the array and therefore can be
> > > > > > considered
> > > > > > constant.
>
> > > > > > > On Aug 20, 1:10 am, L7 <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > This can be done with constant space and O(n) time if you hold
> > > > > > > > to
> > > > > > > > _exactly_ what is mentioned in your post. An integer (32/64)
> > > > > > > > can hold
> > > > > > > > only a finite number of values. Based on that, you can create a
> > > > > > > > bitfield at size log of that mamimum value. You now have
> > > > > > > > constant size
> > > > > > > > 'hashing' where the hash is simply 1 << x[n]. Now the hash is
> > > > > > > > not a
> > > > > > > > problem of growth based on the size of the array. With that
> > > > > > > > implementation of sumedh sakdeo's hash solution you have the
> > > > > > > > problem
> > > > > > > > solved.
>
> > > > > > > > On Aug 19, 1:45 am, dsha <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > Hello,
>
> > > > > > > > > as I already mentioned, there are no any additional
> > > > > > > > > constraints on the
> > > > > > > > > input data, so you cannot assume
> > > > > > > > > that the array is ordered. Nor can you order it, as I presume
> > > > > > > > > that the
> > > > > > > > > input data should remain intact (sorry, I must have mentioned
> > > > > > > > > this
> > > > > > > > > before). So a solution cannot be based upon the assumption
> > > > > > > > > you made.
>
> > > > > > > > > Thanks.
>
> > > > > > > > > On Aug 18, 2:14 pm, "Peeyush Bishnoi" <[EMAIL PROTECTED]>
> > > > > > > > > wrote:
>
> > > > > > > > > > Hello All
> > > > > > > > > > I thanxs Vaibhav to give feedback on my solution....
>
> > > > > > > > > > I am once again putting my solution back on this group. I
> > > > > > > > > > welcome ur all
> > > > > > > > > > valuale feedback on this...
> > > > > > > > > > I can think this solution will work with constant space &
> > > > > > > > > > linear time ....
> > > > > > > > > > incomparison to my previous solution which is n*n at worst
> > > > > > > > > > case.
> > > > > > > > > > But this solution need integer array data set to be
> > > > > > > > > > sorted...
>
> > > > > > > > > > int main(){
> > > > > > > > > > int a[]={1,2,2,3};
> > > > > > > > > > int count=sizeof(a)/sizeof(a[0]);
> > > > > > > > > > printf("No.of elemenst:%d\n",count);
> > > > > > > > > > fun(a,count);
> > > > > > > > > > return 0;
>
> > > > > > > > > > }
>
> > > > > > > > > > fun(int a[],int count){
> > > > > > > > > > int i,j;
> > > > > > > > > > for(i=0,j=i+1;i<count,(i<j &&
> > > > > > > > > > (a[i]!=a[j]));i++,j++);
> > > > > > > > > > if((i<j)&& (a[i]==a[j])){
> > > > > > > > > > printf("No. is
> > > > > > > > > > repeated:%d\n",a[i]);
> > > > > > > > > > }else{
>
> > > > > > > > > > }
>
> > > > > > > > > > }
>
> > > > > > > > > > ---
> > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > On 8/18/07, Vaibhav Jain <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > peeyush,
>
> > > > > > > > > > > take eg: n=6
> > > > > > > > > > > array values: 10 20 30 40 50 50
> > > > > > > > > > > in worst case, while loop which can increment 'i' can go
> > > > > > > > > > > upto n-1
> > > > > > > > > > > and for loop (for 'j') every n-1 time check upto n times
> > > > > > > > > > > so total it becomes (n-1)*n= O(n*n).
>
> > > > > > > > > > > like this i think u can observe now..
>
> > > > > > > > > > > On 8/18/07, Peeyush Bishnoi <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > > Thanxs for giving feedback... :-)
> > > > > > > > > > > > Can you please explain how worst case time complexity
> > > > > > > > > > > > is O(n*n) of
> > > > > > > > > > > > this solution. Means how u determine this. Plz
> > > > > > > > > > > > explain....
>
> > > > > > > > > > > > ---
> > > > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > > > On 8/18/07, Vaibhav Jain <[EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > > > hi peeyush,
>
> > > > > > > > > > > > > ur solution is nice, it is brute force method and
> > > > > > > > > > > > > space complexity is
> > > > > > > > > > > > > constant here
> > > > > > > > > > > > > but ur solution contains worst case time complexity
> > > > > > > > > > > > > O(n*n)
> > > > > > > > > > > > > and we want O(n) solution. So ur solution is not
> > > > > > > > > > > > > required solution.
>
> > > > > > > > > > > > > On 8/18/07, Peeyush Bishnoi < [EMAIL PROTECTED]>
> > > > > > > > > > > > > wrote:
>
> > > > > > > > > > > > > > Hello All ,
>
> > > > > > > > > > > > > > I am thinking this solution offered by me is some
> > > > > > > > > > > > > > what accurate with
> > > > > > > > > > > > > > constant space . Just put ur feed back on this.
>
> > > > > > > > > > > > > > If you have any query ask me.
>
> > > > > > > > > > > > > > int main(){
> > > > > > > > > > > > > > int a[]={1,2,2,3};
> > > > > > > > > > > > > > int count=sizeof(a)/sizeof(a[0]);
> > > > > > > > > > > > > > printf("No.of elemenst:%d\n",count);
> > > > > > > > > > > > > > fun(a,count);
> > > > > > > > > > > > > > return 0;
> > > > > > > > > > > > > > }
>
> > > > > > > > > > > > > > fun(int a[],int count){
> > > > > > > > > > > > > > int i=0,j;
> > > > > > > > > > > > > > while(i<count){
> > > > > > > > > > > > > > for(j=0;(j<i && (a[i]!=a[j]));j++);
> > > > > > > > > > > > > > if((j<i)&& (a[i]==a[j])){
> > > > > > > > > > > > > > printf("No. is
> > > > > > > > > > > > > > repeated:%d\n",a[i]);
> > > > > > > > > > > > > > }else{
> > > > > > > > > > > > > > }
> > > > > > > > > > > > > > i++;
> > > > > > > > > > > > > > }
> > > > > > > > > > > > > > }
>
> > > > > > > > > > > > > > ---
> > > > > > > > > > > > > > Peeyush Bishnoi
>
> > > > > > > > > > > > > > On 8/18/07, Dondi Imperial < [EMAIL PROTECTED] >
> > > > > > > > > > > > > > wrote:
>
> > > > > > > > > > > > > > > hi,
>
> > > > > > > > > > > > > > > actually in mine space complexity is O(n) in
> > > > > > > > > > > > > > > _all_ cases. :). Out
> > > > > > > > > > > > > > > of
> > > > > > > > > > > > > > > curiousity, will your solution work when not all
> > > > > > > > > > > > > > > the numbers in
> > > > > > > > > > > > > > > the
> > > > > > > > > > > > > > > range are present in the array?
>
> > > > > > > > > > > > > > > Thanks,
>
> > > > > > > > > > > > > > > Dondi
>
> > > > > > > > > > > > > > > On 8/17/07, Vaibhav Jain < [EMAIL PROTECTED] >
> > > > > > > > > > > > > > > wrote:
> > > > > > > > > > > > > > > > hello Dondi,
>
> > > > > > > > > > > > > > > > in ur solution, space complexity will be O(n)
> > > > > > > > > > > > > > > > in worst case.
> > > > > > > > > > > > > > > > but in my solution it will constant space with
> > > > > > > > > > > > > > > > linear
> > > > > > > > > > > > > > > complexity.
>
> > > > > > > > > > > > > > > > now think abt how to prove it if range is not
>
> ...
>
> read more >>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
