Welcome, %1$s. Please login or register.

February 26, 2018, 07:27:58 AM
: 1
: swapping 0's and 1's  ( 6102 )
« : June 09, 2007, 12:13:11 PM From satyadb4u»

swapping 0's and 1's

there are randon no of zeroes and ones in a random sized array.  W hats the best possible way to make it so that inittially it has all zeroes then ones...

0 0 1 1 0 1
0 0 0 1 1 1

i repeat most efficient method

Liked It? Share it!


« #1 : June 09, 2007, 01:22:19 PM From Poonam»

I assume you would know the size of the array. Lets say n.

1. Now take 2 pointers one from the start and one from the end (index n-1).
2. Move the first pointer forward till you reach a 1.
3. Move the second pointer backwards till you reach a zero.
4. Swap the two values.
5. Repeat steps 2 to 4 and stop as soon as both pointers point to the same location.

It takes O(n) in terms of time complexity and doesn't need any extra memory ( for the inplace replacement).
« #2 : June 10, 2007, 10:46:07 AM From satyadb4u»

Thats it .Nice answer yaar
« #3 : June 26, 2007, 03:08:20 PM From anil sati»

Add all the elements in the array --- we will get the number of ones.i.e

if the array is 0,0,0,,1,1,0,1 then sum of all elemnets is 3 so now we know the number of lements in arrya so put the last 3 locations as 1 and rest of the first locations as 0
« #4 : June 26, 2007, 08:05:32 PM From Poonam»

Hey Anil, your solution is good.
The only drawback from my solution is that your solution needs 2 times traversing of the array. However it can be more optimised by doing a memset of the array to 0 before changing. This way, we need not traverse the whole array again and can set only the required number of 1s.
« #5 : November 19, 2007, 07:52:49 PM From iammilind»


I think Anil's answer is the most efficient one.
Two time traversal is mandatory.
If 'memset' is used, we will slowing down the process, rather than optimizing it.
Note that, 'memset' is internally a small code of 'for' loop only. :)

consider the following example,
int arr[] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; // one 0 and nineteen 1s

Anil's way :
(i) count the number of 1s in 1st for loop
(ii) use the count to put 1s from end of the array (or from size-n index)
(iii) remaining elements set to 0
(total itterations = 20 + 19 + 1 = 40 )

'memset' way :
(i) count the number of 1s in 1st for loop
(ii) 'memset' the array to 0
(iii) put the 1s (either from beginning or size-n index, no matter)
(total ittereations = 20 + 20 + 19 = 59)
« #6 : November 22, 2007, 11:11:55 PM From spazinvader»

I guess we still optimize Anil's way.
1)Count the number of 1's in the for loop.In the same loop,add an if else condition.
//let n be the size of array
if(N>=(n/2))              //N is the count
2)Now what we have to do is to just check from the back of the array upto    n-N whether they are 1.If not make it as 0.

In this case int a[] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
1)20 for count
2)10 for changing a.

I guess it will be optimal.But i expect even more optimized solutions.
« #7 : November 23, 2007, 12:00:48 PM From iammilind»

@ spazinvader,
Your solution is not clear, plz try to give code in such case.
If I understand properly then what you suggested is an overhead in such cases when no. of 1s are less.
Let see, if we can optimize following (this is according to actual algo, which Anil suggested):

void Arrange_0_then_1 (int a[], int SIZE)
    int j=SIZE,count=SIZE;  //'j' is choosen, since 'i' confused with italic

    while( --j >= 0 )      // We are counting no. of 0s
        count -= a[j];
    while( ++j < count)  // First arrange 0s
         a[j] = 0;
    while( j < SIZE )      // Then arrange 1s
         a[j++] = 1;
« #8 : January 10, 2008, 01:20:27 PM From thequark»

@Guru: Nice answer. The problem is similar to Dutch National Flag problem [http://en.wikipedia.org/wiki/Dutch_national_flag]. DNF has 3 colors with same consideration. Actually the problem _seems_ difficult if 3 colors are present

@I am Milind: The assumption that memset is equivalent or equal to the for loop is not true if you look at execution time. It would be optimized for the platform to accommodate writing a 'word' a time rather than writing a character, short a time which a user program would tend to do. The difference would not be in algorithmic complexity but processing overheads involved in word aligned memory access.
« #9 : January 10, 2008, 06:38:44 PM From iammilind»

'memset' is implemented by loop only that is for sure. Now, how it is implemented that is dependent. You can't avoid loop when you have to deal with thousands of elements.

If we use memset, than that will be acquiring more amount of time. Just look at the example I gave in earlier post (single 0 and all 1s).

Why I said Anil's answer was best, because there is no assumption of "known array size" is required, (while counting either 1s or 0s we can keep track of the length also). Just it has to be implemented in more sophisticated way.
« #10 : January 10, 2008, 09:57:54 PM From thequark»

i accept it is a for loop and it is a for loop for sure.
my subtle point was that


and for (i=0;i<10;i++)
    p = 0;

are not one and the same. I am demarcating a difference between the two.

In all the architectures processors are build to read/write a 'word' at a time. So if you read a character further masking has to be done to get only a single byte out of word. If a datastructure equals two words then two reads/writes to read/write 1 word.

Still worse if your processor doesnt support such things the compiler has to generate code to do so. These have process overheads. Memset created for a specific platform will be made taking care of this. So even if p is a character the for loop inside memset _should_ be made to write 4 bytes (which is word size supported by processor) at a time into the buffer and write the left over buffer individually.
« #11 : January 30, 2011, 04:20:03 PM From badboy711»

: 1
« previous next »


Best RatedList All>>


SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer