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. 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)
> > > > > > > > > > > > > > if(arrayLookup[i] > 0) then
> > > > > > > > > > > > > > found
> > > > > > > > > > > > > > else
> > > > > > > > > > > > > > arrayLookup[i]++
>
> > > > > > > > > > > > > > Of course range could be prohibitively large (still
> > > > > > > > > > > > > > constant
> > > > > > > > > > > > though if
> > > > > > > > > > > > > > you know the range before hand).
>
> > > > > > > > > > > > > > On 8/17/07, Vaibhav Jain < [EMAIL PROTECTED]> wrote:
> > > > > > > > > > > > > > > if u know the range of values stored in array then
> > > > > > > > > > > > > > > let me assume values 1 to k then u can calculate
> > > > > > > > > > > > > > > sum of
> > > > > > > > > > > > numbers stored
> > > > > > > > > > > > > in
> > > > > > > > > > > > > > > array in O(n) complexity.
> > > > > > > > > > > > > > > after that apply formula
>
> > > > > > > > > > > > > > > duplicate value= [k*(k+1)]/2 - sum of numbers
> > > > > > > > > > > > > > > stored in
> > > > > > > > > > > > array
>
> > > > > > > > > > > > > > > it will take O(1) constant time so total
> > > > > > > > > > > > > > > complexity becomes
> > > > > > > > > > > > only O(n).
>
> > > > > > > > > > > > > > > it can be one solution to your problem but if the
> > > > > > > > > > > > > > > range is
> > > > > > > > > > > > unknown for
> > > > > > > > > > > > > > > values then
> > > > > > > > > > > > > > > is there any solution to come in O(n)???
>
> > > > > > > > > > > > > > > On 8/16/07, dsha < [EMAIL PROTECTED]> wrote:
>
> > > > > > > > > > > > > > > > Hi there,
>
> > > > > > > > > > > > > > > > I'm interested in the following problem: there
> > > > > > > > > > > > > > > > is an array
> > > > > > > > > > > > of integers
> > > > > > > > > > > > > > > > that contains each element only once except for
> > > > > > > > > > > > > > > > one
> > > > > > > > > > > > element that
> > > > > > > > > > > > > > > > occurs exactly twice. Is there a way to find
> > > > > > > > > > > > > > > > this element
> > > > > > > > > > > > faster than
> > > > > > > > > > > > > > > > O(n*log n) and with constant extra memory? If
> > > > > > > > > > > > > > > > no, how can
> > > > > > > > > > > > I prove it?
>
> ...
>
> 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
-~----------~----~----~----~------~----~------~--~---
