Solution 1 for Scaler Topics Fortnightly Contest - 28
Lucky Number
This article is part of the Scaler Topics Fortnightly Contest - 28
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
Solution Approach
Let’s recall the conditions under which we can rearrange the letters of a word to form a palindrome. This is achievable if the number of letters with odd occurrences is not greater than 1.
In our problem, it suffices to verify that the number of letters with odd occurrences (denoted as x) is not greater than A+1. Let’s prove this assertion.
If x>A+1, then it is impossible to obtain the answer because, with A operations, we cannot reduce the number of letters with odd occurrences to not be greater than 1. On the other hand, we can simply remove the character with an odd number of occurrences in each removal iteration and decrease the number of odd occurrences. If there are no such characters, we can choose any character and remove it, thus ensuring there is only 1 character with an odd occurrence.
Time complexity : O(B.size()) Space complexity: O(1)
C++ Implementation
Java 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
