Longest sequence such that no two adjacent element are of same type
source link: https://www.geeksforgeeks.org/longest-sequence-such-that-no-two-adjacent-element-are-of-same-type/?utm_campaign=newhomepage
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Longest sequence such that no two adjacent element are of same type
- Difficulty Level : Medium
- Last Updated : 12 Dec, 2022
Given an array arr[] of size N, where each value represents the number of elements present of the ith type, the task is to find the longest sequence that can be made such that no two adjacent elements are of the same type.
Examples:
Input: N = 3, arr[] = {7, 3, 2}
Output: 11
Explanation:
In the above example there are three types of elements which are type0, type1, and type2.
We have 7 elements of type0, 3 of type1, 2 of type2.
Maximum of 11 elements can be placed in a row such that no two adjacents are the same.
t0, t1, t0, t1, t0, t1, t0, t2, t0, t2, t0.Input: N = 2, arr[] = {3, 6}
Output: 7
Explanation: t1, t0, t1, t0, t1, t0, t1. Here, we can see a maximum length of 7 is possible.
Approach: The problem can be solved based on the following idea:
We can use a two-pointer algorithm here on the sorted array. To get the maximum length, we need to get the maximum number of elements of a different type. For that just maintain two pointers one on starting and another on ending in a sorted array. Keep on adding elements of array arr[] in the sequence.
Follow the below steps to implement the idea:
- First of all, sort the array.
- Now use the two-pointer approach. One pointer will move from the start and one from the end.
- As the sum of the first pointer elements decreases from the last pointer elements, add more elements to the first pointer that is move over the first pointer ahead and vice-versa.
- Let’s say a minimum of both is min then our answer will be min * 2 + 1 and if both are the same then our answer will be min*2 because we will place each ball from both one by one.
Below is theimplementationof the above approach.
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find maximum length of arrangementint maxLength(int N, vector<int>& arr){// If only one type of elements are presentif (N == 1)return 1;// Sorting the arraysort(arr.begin(), arr.end());// presum and postsumint sum1 = arr[0], sum2 = arr[N - 1], ans;// This below if-else loop is for array// of size 2.if (sum1 == sum2) {ans = 2 * sum1;}else {int t = min(sum1, sum2);ans = t * 2 + 1;}// Setting the first pointer on second element// from start setting the second pointer on// second-last element.int i = 1, j = N - 2;while (i <= j) {// If presum become smaller of equal// then move first pointer else// move second pointerif (sum1 <= sum2) {sum1 += arr[i];i++;}else {sum2 += arr[j];j--;}// If both sum are equal then// answer will be total sumif (sum1 == sum2) {ans = 2 * sum1;}else {int t = min(sum1, sum2);ans = t * 2 + 1;}}// Return maximum length possiblereturn ans;}// Driver Codeint main(){vector<int> arr = { 7, 3, 2 };int N = arr.size();// Function callcout << maxLength(N, arr) << endl;return 0;} |
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Related Articles:
.png)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK