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 the implementation of the above approach.
C++
// 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 present if (N == 1) return 1; // Sorting the array sort(arr.begin(), arr.end()); // presum and postsum int 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 pointer if (sum1 <= sum2) { sum1 += arr[i]; i++; } else { sum2 += arr[j]; j--; } // If both sum are equal then // answer will be total sum if (sum1 == sum2) { ans = 2 * sum1; } else { int t = min(sum1, sum2); ans = t * 2 + 1; } } // Return maximum length possible return ans;}// Driver Codeint main(){ vector<int> arr = { 7, 3, 2 }; int N = arr.size(); // Function call cout << maxLength(N, arr) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class Main { // Function to find maximum length of arrangement static int maxLength(int N, int[] arr) { // If only one type of elements are present if (N == 1) return 1; // Sorting the array Arrays.sort(arr); // presum and postsum int 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 = Math.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 pointer if (sum1 <= sum2) { sum1 += arr[i]; i++; } else { sum2 += arr[j]; j--; } // If both sum are equal then // answer will be total sum if (sum1 == sum2) { ans = 2 * sum1; } else { int t = Math.min(sum1, sum2); ans = t * 2 + 1; } } // Return maximum length possible return ans; } public static void main(String[] args) { int[] arr = { 7, 3, 2 }; int N = arr.length; System.out.println(maxLength(N, arr)); }}// This code is contributed by lokesh. |
Python3
# python codedef maxLength(N, arr): # If only one type of elements are present if N == 1: return 1 # Sorting the array arr = sorted(arr) # presum and postsum sum1 = arr[0] sum2 = arr[N - 1] ans = 0 # This below if-else loop is for array # of size 2. if sum1 == sum2: ans = 2 * sum1 else: 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. i = 1 j = N - 2 while i <= j: # If presum become smaller of equal # then move first pointer else # move second pointer if sum1 <= sum2: sum1 += arr[i] i += 1 else: sum2 += arr[j] j -= 1 # If both sum are equal then # answer will be total sum if sum1 == sum2: ans = 2 * sum1 else: t = min(sum1, sum2) ans = t * 2 + 1 # Return maximum length possible return ans# Test codearr = [7, 3, 2]N = len(arr)print(maxLength(N, arr))# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;class GFG { // Function to find maximum length of arrangement static int maxLength(int N, int[] arr) { // If only one type of elements are present if (N == 1) return 1; // Sorting the array Array.Sort(arr); // presum and postsum int 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 = Math.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 pointer if (sum1 <= sum2) { sum1 += arr[i]; i++; } else { sum2 += arr[j]; j--; } // If both sum are equal then // answer will be total sum if (sum1 == sum2) { ans = 2 * sum1; } else { int t = Math.Min(sum1, sum2); ans = t * 2 + 1; } } // Return maximum length possible return ans; } public static void Main() { int[] arr = { 7, 3, 2 }; int N = arr.Length; Console.WriteLine(maxLength(N, arr)); }}// This code is contributed by Pushpesh Raj. |
Javascript
// Javascript code to implement the approach// Function to find maximum length of arrangementfunction maxLength(N, arr){ // If only one type of elements are present if (N == 1) return 1; // Sorting the array arr.sort(); // presum and postsum let 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 { let t = Math.min(sum1, sum2); ans = t * 2 + 1; } // Setting the first pointer on second element // from start setting the second pointer on // second-last element. let i = 1, j = N - 2; while (i <= j) { // If presum become smaller of equal // then move first pointer else // move second pointer if (sum1 <= sum2) { sum1 += arr[i]; i++; } else { sum2 += arr[j]; j--; } // If both sum are equal then // answer will be total sum if (sum1 == sum2) { ans = 2 * sum1; } else { let t = Math.min(sum1, sum2); ans = t * 2 + 1; } } // Return maximum length possible return ans;}// Driver Code let arr = [7, 3, 2]; let N = arr.length; // Function call console.log(maxLength(N, arr)); // This code is contributed by poojaagarwal2. |
Output
11
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
