Saturday, June 25, 2022
HomeWordPress DevelopmentSegregate 0s and 1s in an array
WordPress Development

Segregate 0s and 1s in an array

Admin
By Admin
0
1


You might be given an array of 0s and 1s in random order. Segregate 0s on left aspect and 1s on proper aspect of the array [Basically you have to sort the array]. Traverse array solely as soon as. 

Enter array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Methodology 1 (Rely 0s or 1s) 
Due to Naveen for suggesting this methodology. 
1) Rely the variety of 0s. So let’s perceive with an instance we have now an array arr = [0, 1, 0, 1, 0, 0, 1] the dimensions of the array is 7 now we’ll traverse your complete array and discover out the variety of zeros within the array, On this case the variety of zeros is 4 so now we will simply get the variety of Ones within the array by Array Size – Quantity Of Zeros.

2) As soon as we have now counted, we will fill the array first we’ll put the zeros after which ones (we will get variety of ones through the use of above method).

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

 

void segregate0and1(int arr[], int n)

{

    int rely = 0;

 

    for (int i = 0; i < n; i++) {

        if (arr[i] == 0)

            rely++;

    }

 

    

    for (int i = 0; i < rely; i++)

        arr[i] = 0;

 

    

    for (int i = rely; i < n; i++)

        arr[i] = 1;

}

 

void print(int arr[], int n)

{

    cout << "Array after segregation is ";

 

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

 

int most important()

{

    int arr[] = { 0, 1, 0, 1, 1, 1 };

    int n = sizeof(arr) / sizeof(arr[0]);

     

    segregate0and1(arr, n);

    print(arr, n);

     

    return 0;

}

 

Java

class GFG {

     

    

    static void segregate0and1(int arr[], int n)

    {

        int rely = 0;

     

        for (int i = 0; i < n; i++) {

            if (arr[i] == 0)

                rely++;

        }

 

        

        for (int i = 0; i < rely; i++)

            arr[i] = 0;

 

        

        for (int i = rely; i < n; i++)

            arr[i] = 1;

    }

     

    

    static void print(int arr[], int n)

    {

        System.out.print("Array after segregation is ");

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");   

    }

     

    

    public static void most important(String[] args)

    {

        int arr[] = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.size;

 

        segregate0and1(arr, n);

        print(arr, n);

         

    }

}

 

Python3

 

def segregate0and1(arr, n) :

     

    

    rely = 0

 

    for i in vary(0, n) :

        if (arr[i] == 0) :

            rely = rely + 1

 

    

    for i in vary(0, rely) :

        arr[i] = 0

 

    

    for i in vary(rely, n) :

        arr[i] = 1

         

 

def print_arr(arr , n) :

    print( "Array after segregation is ",finish = "")

 

    for i in vary(0, n) :

        print(arr[i] , finish = " ")

         

 

arr = [ 0, 1, 0, 1, 1, 1 ]

n = len(arr)

     

segregate0and1(arr, n)

print_arr(arr, n)

 

 

         

C#

utilizing System;

 

class GFG {

     

    

    static void segregate0and1(int []arr, int n)

    {  

        

        int rely = 0;

     

        for (int i = 0; i < n; i++) {

            if (arr[i] == 0)

                rely++;

        }

 

        

        for (int i = 0; i < rely; i++)

            arr[i] = 0;

 

        

        for (int i = rely; i < n; i++)

            arr[i] = 1;

    }

     

    

    static void print(int []arr, int n)

    {

        Console.WriteLine("Array after segregation is ");

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

    }

     

    

    public static void Fundamental()

    {

        int []arr = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.Size;

 

        segregate0and1(arr, n);

        print(arr, n);

         

    }

}

 

PHP

<?php

 

operate segregate0and1(&$arr, $n)

{

    $rely = 0;

                

 

    for ($i = 0; $i < $n; $i++)

    {

        if ($arr[$i] == 0)

            $rely++;

    }

 

    

    

    for ($i = 0; $i < $rely; $i++)

        $arr[$i] = 0;

 

    

    

    for ($i = $rely; $i < $n; $i++)

        $arr[$i] = 1;

}

 

operate toprint(&$arr , $n)

{

    echo ("Array after segregation is ");

 

    for ($i = 0; $i < $n; $i++)

        echo ( $arr[$i] . " ");

}

 

$arr = array(0, 1, 0, 1, 1, 1 );

$n = sizeof($arr);

 

segregate0and1($arr, $n);

toprint($arr, $n);

     

?>

Javascript

<script>

 

operate segregate0and1(arr, n)

{

    let rely = 0;

 

    for (let i = 0; i < n; i++) {

        if (arr[i] == 0)

            rely++;

    }

 

    

    for (let i = 0; i < rely; i++)

        arr[i] = 0;

 

    

    for (let i = rely; i < n; i++)

        arr[i] = 1;

}

 

operate print(arr, n)

{

    doc.write("Array after segregation is ");

 

    for (let i = 0; i < n; i++)

        doc.write(arr[i] + " ");

}

 

 

    let arr = [ 0, 1, 0, 1, 1, 1 ];

    let n = arr.size;

     

    segregate0and1(arr, n);

    print(arr, n);

     

 

 

</script>
Output

Array after segregation is 0 0 1 1 1 1

Time Complexity : O(2n)  ≅ O(n)
Auxiliary Area: O(1)

Methodology 1 traverses the array two occasions. Methodology 2 does the identical in a single cross.

Methodology 1 has time complexity of O(2n) and Methodology 2 has time complexity of O(n)

Methodology 2 (Use two indexes to traverse) 
Keep two indexes. Initialize the primary index left as 0 and second index proper as n-1.
Do following whereas left < proper 
a) Preserve incrementing index left whereas there are 0s at it 
b) Preserve decrementing index proper whereas there are 1s at it 
c) If left < proper then change arr[left] and arr[right]

Implementation: 

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

 

void segregate0and1(int arr[], int measurement)

{

    

    int left = 0, proper = size-1;

 

    whereas (left < proper)

    {

        

        whereas (arr[left] == 0 && left < proper)

            left++;

 

        

        whereas (arr[right] == 1 && left < proper)

            right--;

 

        

        

        if (left < proper)

        {

            arr[left] = 0;

            arr[right] = 1;

            left++;

            right--;

        }

    }

}

 

int most important()

{

    int arr[] = {0, 1, 0, 1, 1, 1};

    int i, arr_size = sizeof(arr)/sizeof(arr[0]);

 

    segregate0and1(arr, arr_size);

 

    cout << "Array after segregation ";

    for (i = 0; i < 6; i++)

        cout << arr[i] << " ";

    return 0;

}

 

C

#embrace<stdio.h>

 

void segregate0and1(int arr[], int measurement)

{

    

    int left = 0, proper = size-1;

 

    whereas (left < proper)

    {

        

        whereas (arr[left] == 0 && left < proper)

            left++;

 

        

        whereas (arr[right] == 1 && left < proper)

            right--;

 

        

          

        if (left < proper)

        {

            arr[left] = 0;

            arr[right] = 1;

            left++;

            right--;

        }

    }

}

 

int most important()

{

    int arr[] = {0, 1, 0, 1, 1, 1};

    int i, arr_size = sizeof(arr)/sizeof(arr[0]);

 

    segregate0and1(arr, arr_size);

 

    printf("Array after segregation ");

    for (i = 0; i < 6; i++)

        printf("%d ", arr[i]);

 

    getchar();

    return 0;

}

Java

class Segregate

{

    

    void segregate0and1(int arr[], int measurement)

    {

        

        int left = 0, proper = measurement - 1;

 

        whereas (left < proper)

        {

            

            whereas (arr[left] == 0 && left < proper)

               left++;

 

            

            whereas (arr[right] == 1 && left < proper)

                right--;

 

            

               

            if (left < proper)

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

     

    

    public static void most important(String[] args)

    {

        Segregate seg = new Segregate();

        int arr[] = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.size;

 

        seg.segregate0and1(arr, arr_size);

 

        System.out.print("Array after segregation is ");

        for (i = 0; i < 6; i++)

            System.out.print(arr[i] + " ");

    }

}

Python

 

def segregate0and1(arr, measurement):

    

    left, proper = 0, measurement-1

     

    whereas left < proper:

        

        whereas arr[left] == 0 and left < proper:

            left += 1

 

        

        whereas arr[right] == 1 and left < proper:

            proper -= 1

 

        

        

        if left < proper:

            arr[left] = 0

            arr[right] = 1

            left += 1

            proper -= 1

 

    return arr

 

arr = [0, 1, 0, 1, 1, 1]

arr_size = len(arr)

print("Array after segregation")

print(segregate0and1(arr, arr_size))

 

C#

utilizing System;

 

class Segregate

{

    

      

    void segregate0and1(int []arr, int measurement)

    {

        

        int left = 0, proper = measurement - 1;

 

        whereas (left < proper)

        {

            

               

            whereas (arr[left] == 0 && left < proper)

            left++;

 

            

               

            whereas (arr[right] == 1 && left < proper)

                right--;

 

            

               

               

            if (left < proper)

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

     

    

    public static void Fundamental()

    {

        Segregate seg = new Segregate();

        int []arr = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.Size;

 

        seg.segregate0and1(arr, arr_size);

 

        Console.WriteLine("Array after segregation is ");

        for (i = 0; i < 6; i++)

            Console.Write(arr[i] + " ");

    }

}

 

PHP

<?php

 

operate segregate0and1(&$arr, $measurement)

{

    

    

    $left = 0;

    $proper = $measurement - 1;

 

    whereas ($left < $proper)

    {

        

        

        whereas ($arr[$left] == 0 &&

               $left < $proper)

            $left++;

 

        

        

        whereas ($arr[$right] == 1 &&

               $left < $proper)

            $proper--;

 

        

        

        

        

        if ($left < $proper)

        {

            $arr[$left] = 0;

            $arr[$right] = 1;

            $left++;

            $proper--;

        }

    }

}

 

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

 

segregate0and1($arr, $arr_size);

 

printf("Array after segregation is ");

for ($i = 0; $i < 6; $i++)

    echo ($arr[$i]. " ");

 

?>

Javascript

<script>

 

 

operate segregate0and1(arr, measurement)

{

    

    let left = 0, proper = size-1;

 

    whereas (left < proper)

    {

        

        whereas (arr[left] == 0 && left < proper)

            left++;

 

        

        whereas (arr[right] == 1 && left < proper)

            right--;

 

        

        

        if (left < proper)

        {

            arr[left] = 0;

            arr[right] = 1;

            left++;

            right--;

        }

    }

}

 

let arr = [0, 1, 0, 1, 1, 1];

let i, arr_size = arr.size;

 

segregate0and1(arr, arr_size);

 

doc.write("Array after segregation ");

for (i = 0; i < 6; i++)

    doc.write(arr[i] + " ");

 

</script>
Output

Array after segregation 0 0 1 1 1 1

Time Complexity : O(n) 
Auxiliary Area: O(1)

One other method : 
1. Take two pointer type0(for aspect 0) ranging from starting (index = 0) and type1(for aspect 1) ranging from finish (index = array.length-1). 
Initialize type0 = 0 and type1 = array.length-1 
2. It’s meant to Put 1 to the precise aspect of the array. As soon as it’s performed, then 0 will certainly in direction of the left aspect of the array.

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

 

void segregate0and1(int arr[], int measurement)

{

    int type0 = 0;

    int type1 = measurement - 1;

 

    whereas (type0 < type1) {

        if (arr[type0] == 1) {

            if (arr[type1] != 1) {

                swap(arr[type0], arr[type1]);

            }

            type1--;

        }

        else

            type0++;

    }

}

 

int most important()

{

    int arr[] = { 0, 1, 0, 1, 1, 1 };

    int i, arr_size = sizeof(arr) / sizeof(arr[0]);

 

    segregate0and1(arr, arr_size);

 

    cout << "Array after segregation is ";

    for (i = 0; i < arr_size; i++)

        cout << arr[i] << " ";

 

    return 0;

}

Java

import java.util.*;

 

class GFG {

    /**

    Methodology for segregation 0 and 1 given enter array

    */

    static void segregate0and1(int arr[])

    {

        int type0 = 0;

        int type1 = arr.size - 1;

 

        whereas (type0 < type1) {

            if (arr[type0] == 1) {

                if (arr[type1] != 1) {

                    

                    arr[type1] = arr[type1] + arr[type0];

                    arr[type0] = arr[type1] - arr[type0];

                    arr[type1] = arr[type1] - arr[type0];

                }

                type1--;

            }

            else {

                type0++;

            }

        }

    }

 

    

    public static void most important(String[] args)

    {

 

        int[] array = { 0, 1, 0, 1, 1, 1 };

 

        segregate0and1(array);

 

        for (int a : array) {

            System.out.print(a + " ");

        }

    }

}

Python3

 

 

 

def segregate0and1(arr, measurement):

 

    type0 = 0

    type1 = measurement - 1

 

    whereas(type0 < type1):

        if(arr[type0] == 1):

            if(arr[type1] != 1):

              (arr[type0],

               arr[type1]) = (arr[type1],

                              arr[type0])

            type1 -= 1

        else:

            type0 += 1

     

arr = [0, 1, 0, 1, 1, 1]

arr_size = len(arr)

segregate0and1(arr, arr_size)

print("Array after segregation is",

                         finish = " ")

for i in vary(0, arr_size):

        print(arr[i], finish = " ")

 

C#

utilizing System;

 

class GFG {

 

    

    

    static void segregate0and1(int[] arr)

    {

        int type0 = 0;

        int type1 = arr.Size - 1;

 

        whereas (type0 < type1) {

            if (arr[type0] == 1) {

                if (arr[type1] != 1) {

                    

                    arr[type1] = arr[type1] + arr[type0];

                    arr[type0] = arr[type1] - arr[type0];

                    arr[type1] = arr[type1] - arr[type0];

                }

                type1--;

            }

 

            else {

                type0++;

            }

        }

    }

 

    

    public static void Fundamental(string[] args)

    {

 

        int[] array = new int[] { 0, 1, 0, 1, 1, 1 };

        segregate0and1(array);

 

        Console.Write("Array after segregation is ");

        foreach(int a in array) { Console.Write(a + " "); }

    }

}

 

PHP

<?php

 

operate segregate0and1(&$arr , $measurement)

{

    $type0 = 0;

    $type1 = $measurement - 1;

     

    whereas($type0 < $type1)

    {

        if($arr[$type0] == 1)

        {

              if($arr[$type1] != 1)

            {

              $temp = $arr[$type0];

              $arr[$type0] = $arr[$type1];

              $arr[$type1] = $temp;

            }

            $type1--;

        }

        else

        $type0++;

    }

}

 

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

 

segregate0and1($arr, $arr_size);

 

echo ("Array after segregation is ");

for ($i = 0; $i < $arr_size; $i++)

    echo ($arr[$i] . " ");

 

?>

Javascript

<script>

 

 

operate segregate0and1(arr, measurement)

{

    let type0 = 0;

    let type1 = measurement - 1;

     

    whereas (type0 < type1)

    {

        if (arr[type0] == 1)

        {

             if (arr[type1] != 1)

            {  

              

              arr[type1] = arr[type1] + arr[type0];

              arr[type0] = arr[type1] - arr[type0];

              arr[type1] = arr[type1] - arr[type0];

             }

            type1--;

        }

        else

            type0++;

    }

}

 

let arr = [ 0, 1, 0, 1, 1, 1 ];

let i, arr_size = arr.size;

 

segregate0and1(arr, arr_size);

 

doc.write("Array after segregation is ");

for(i = 0; i < arr_size; i++)

    doc.write(arr[i] + " ");

     

 

</script>
Output

Array after segregation is 0 0 1 1 1 1

Time complexity: O(n)

Auxiliary Area: O(1)
// Thanks san4net for suggesting this methodology.
 

Please write feedback should you discover any of the above algorithms/code incorrect, or a greater approach to clear up the identical downside.
 

Vote for issue

Present issue :
Simple





Previous articleReturn to Sender: Mail-in Rebates Are Unhealthy Offers for PC Builders
Admin
Adminhttps://www.handla.it
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Load more

Recent Comments

ABOUT US

handla.it is your computer, laptop, software and cyber security website. We provide you with the latest breaking news and videos straight from the computer industry.

POPULAR POSTS

POPULAR CATEGORY

copyright 2022 © handla.it. All rights reserved.