loading...

Daily HackerRank Challenge - Day 20

wingkwong profile image Wing-Kam 惻3 min read

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

About

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.


New Year Chaos

image

Two points to bear in mind while solving this problem:

  • A person can bribe the one who is sitting just in front of him. The opposite is not possible.
  • A person can bribe atmost 2 different persons.

Keeping this in mind, let's have a look at testcase-1.

First case:

Current position : 5 1 2 3 7 8 6 4
Initial position : 1 2 3 4 5 6 7 8
In the first test, the person-5 has occupied 1st seat. That means he has to bribe 4 persons in front of him to reach on the 1st seat So he violated the second rule here. So that answer is "Too chaotic" without further speculation.

for(int i=q.size()-1;i>=0;i--){
    if(q[i]-(i+1)>2){
        cout << "Too chaotic" << "\n";
        return;
    }
// ...
}

Second case:

Current position : 1 2 5 3 7 8 6 4
Initial position : 1 2 3 4 5 6 7 8
So how did person-4 occupy at position 8? As per the rules, it's not possible for person-4 to bribe persons who are sitting behind him. Instead person 5, 6, 7 & 8 bribed person-4 as he is sitting in front of them. Here is the trasition from initial position to the current position.

1 2 3 4 5 6 7 8 : 0 swap (initial)
1 2 3 5 4 6 7 8 : 1 swap (5 and 4)
1 2 3 5 6 4 7 8 : 1 swap (6 and 4)
1 2 3 5 6 7 4 8 : 1 swap (7 and 4)
1 2 3 5 6 7 8 4 : 1 swap (8 and 4)
1 2 5 3 6 7 8 4 : 1 swap (5 and 3)
1 2 5 3 7 6 8 4 : 1 swap (7 and 6)
1 2 5 3 7 8 6 4 : 1 swap (8 and 6)
Obviously no person violated the second rule here. Hence the output is minimum number of swaps 7.

for(int i=q.size()-1;i>=0;i--){
    // ...
    for(int j=max(q[i]-2,0);j<i;j++){
        if(q[j]>q[i]) ans++;
    }
}

We do not need to sort for this question. Instead, we count how many times q[i] is being bribed. If a number which is greater than q[i] can be found from max(q[i-2],0) to current i, that means this number has bribed q[i]. Since q[i]-2 can be negative, we need to safeguard it by setting it to 0 for this case.

Final Solution

void minimumBribes(vector<int> q) {
    int ans=0;
    for(int i=q.size()-1;i>=0;i--){
        // A person can bribe atmost 2 different persons
        if(q[i]-(i+1)>2){
            cout << "Too chaotic" << "\n";
            return;
        }

        for(int j=max(q[i]-2,0);j<i;j++){
            if(q[j]>q[i]) ans++;
        }
    }
    cout << ans << "\n";
}

Minimum Swaps 2

image

We can keep swapping the same index until the value matches the current index i.

swap(arr[i], arr[arr[i]-1]);
i   arr                        ans
0   [7, 1, 3, 2, 4, 5, 6]      0
0   [6, 1, 3, 2, 4, 5, 7]      1
0   [5, 1, 3, 2, 4, 6, 7]      2
0   [4, 1, 3, 2, 5, 6, 7]      3
0   [2, 1, 3, 4, 5, 6, 7]      4
0   [1, 2, 3, 4, 5, 6, 7]      5

If it matches, check for the next index.

if(arr[i]==i+1) continue;

Final Solution

int minimumSwaps(vector<int> arr) {
    int ans=0;
    for(int i=0;i<arr.size();i++){
        if(arr[i]==i+1) continue;
        swap(arr[i], arr[arr[i]-1]);
        ans++; i--;
    }
    return ans;
}


Complete Code

Check out the complete code via below links

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide