dsa_using_cpp/twoPointerProblems.cpp at main · rajendrapancholi/dsa_using_cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <vector>

using namespace std;

void sortZerosAndOnes(vector<int> &v) // (&v)passing address of the vector becouse not extra memory reserve by copy of the vector.
{
    // int leftPtr = 0;
    // int rightPtr = v.size() - 1;

    // Q1: Sort an array consisting of the only 0s and 1s.
    // M1:  without two pointers.
    // int countZeros = 0;
    // for (int i = 0; i < v.size(); i++)
    // {
    //     if (v[i] == 0)
    //     {
    //         countZeros++;
    //     }
    // }
    // for (int i = 0; i < v.size(); i++)
    // {
    //     if (i < countZeros)
    //     {
    //         v[i] = 0;
    //     }
    //     else
    //     {
    //         v[i] = 1;
    //     }
    // }
    // M2: with two pointers.
    int leftPtr = 0;
    int rightPtr = v.size() - 1;
    while (leftPtr < rightPtr)
    {
        if (v[leftPtr] == 1 && v[rightPtr] == 0)
        {
            v[leftPtr] = 0;
            v[rightPtr] = 1;
            leftPtr++;
            rightPtr--;
        }
        if (v[leftPtr] == 0)
        {
            leftPtr++;
        }
        if (v[rightPtr] == 1)
        {
            rightPtr--;
        }
    }

    // Q2: Given an array of integers 'a', moving all the even integers at the beginning of the array followed by all the odd integers. the relative order of odd or even integers does not matter. Return any array that satisfies the condition.
    // while (leftPtr < rightPtr)
    // {
    //     if (v[leftPtr] % 2 == 1 && v[rightPtr] % 2 == 0)
    //     {
    //         // using inbuild method swap
    //         swap(v[leftPtr], v[rightPtr]);
    //         leftPtr++;
    //         rightPtr--;
    //     }
    //     if (v[leftPtr] % 2 == 0)
    //     {
    //         leftPtr++;
    //     }
    //     if (v[rightPtr] % 2 == 0)
    //     {
    //         rightPtr--;
    //     }
    // }

    return;
}
int main()
{
    cout << "Enter size of the array: ";
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        int ele;
        cin >> ele;
        v.push_back(ele);
    }

    sortZerosAndOnes(v);

    // Display elements of the vector.
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }

    cout << endl;
    return 0;
}