Solution 2 for Scaler Topics Fortnightly Contest - 25
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Mesmerizing Necklace Arrangement
This article is part of the Scaler Topics Fortnightly Contest - 25
Solution Approach
We’ll utilize two arrays: prefixR[i] to represent the count of ‘R’ beads in the prefix of length i and prefixB[i] to denote the count of ‘B’ beads in the prefix of length i.
Consider two positions, i and j, where 0 ≤ i ≤ j ≤ n. Our objective is to remove all ‘B’ beads from the prefix ending at position i, from the suffix starting at position j, and also all ‘R’ beads between positions i and j. The minimum number of beads needed to be removed can be calculated as prefixB[i] + (prefixB[N] - prefixB[j]) + (prefixR[j] - prefixR[i]).
To achieve this, we can employ a two-pointer approach using nested loops. Iterate through all possible positions of i and j and compute the answer by considering the given conditions.
Time Complexity: O(N * N) Space Complexity: O(2 * N)
C++ Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
