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
> > > > > > > > > > > > > > > known for numbers
> > > > > > > > > > > > > > > then can we achieve it or not?
> > > > > > > > > > > > > > > if not then prove it....???
>
> > > > > > > > > > > > > > > On 8/17/07, Dondi Imperial < [EMAIL PROTECTED]>
> > > > > > > > > > > > > > > wrote:
>
> > > > > > > > > > > > > > > > if you know the range of the numbers don't you
> > > > > > > > > > > > > > > > just have to
> > > > > > > > > > > > > > create and
> > > > > > > > > > > > > > > > array (of length k in your example) then
> > > > > > > > > > > > > > > > iterate over the
> > > > > > > > > > > > > > array and
> > > > > > > > > > > > > > > > increment the corresponding element in the
> > > > > > > > > > > > > > > > other array.
>
> > > > > > > > > > > > > > > > Ie,
>
> > > > > > > > > > > > > > > > int[] arrayValues = some array of a known range
> > > > > > > > > > > > > > > > int[] arrayLookup = int[min_in_range -
> > > > > > > > > > > > > > > > max_in_range + 1]
>
> > > > > > > > > > > > > > > > foreach(i in arrayValues)
>
> ...
>
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
