Kids love to play with colors but currently, there is a supply of only 2 types of colors (Red represented by R and Green represented by G). Due to the festive season, each of the kids has colored their houses with either green or red color.
Monk is given the task of distributing sweets Q a number of times. Every time he is asked to travel from house to house to distribute the sweets.
The distribution strategy is that he starts from house and he has to give 1 sweet to a house only when he travels from a greenhouse to a red house or vice-versa. Monk can travel from house to house either in the clockwise direction or in the anti-clockwise direction.
Monk wants your help to find the minimum number of sweets he should carry to complete his journey.
Example:
Input: n = 5, q = 2, s = "RRRGG", queries={{1,5},{3,2}}
Output:
1 0
Approach:
C++
#include <bits/stdc++.h>using namespace std;void colourfulHouses(string s, int n, int q,vector<vector<int>> &queries){for (int i = 0; i < q; i++){int l = queries[i][0], r = queries[i][1];if (l < r){l = l - 1;r = r - 1;int cnt = 0, ans = INT_MAX;for (int i = l; i < r; i++)if (s[i] != s[i + 1])cnt++;ans = min(ans, cnt);cnt = 0;for (int i = l; i > 0; i--)if (s[i] != s[i - 1])cnt++;if (s[0] != s[n - 1])cnt++;for (int i = n - 2; i >= r; i--)if (s[i] != s[i + 1])cnt++;ans = min(ans, cnt);cout << ans << "\n";}else{l = l - 1;r = r - 1;int cnt = 0, ans1 = INT_MAX;for (int i = l; i > r; i--)if (s[i] != s[i - 1])cnt++;ans1 = min(ans1, cnt);cnt = 0;for (int i = l; i < n - 1; i++)if (s[i] != s[i + 1])cnt++;if (s[0] != s[n - 1])cnt++;for (int i = 0; i < r; i++)if (s[i] != s[i + 1])cnt++;ans1 = min(ans1, cnt);cout << ans1 << "\n";}}}int main(){int n = 5, q = 2;string s = "RRRGG";vector<vector<int>> queries = {{1, 5}, {3, 2}};colourfulHouses(s, n, q, queries);return 0;}
No comments:
Post a Comment