Solution 1 for Scaler Topics Fortnightly Contest - 28

Learn via video courses
Topics Covered

Lucky Number

This article is part of the Scaler Topics Fortnightly Contest - 28

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration
AI-LedCurriculum
Career SupportSupport
Program highlights
Go to Program
NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program

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

Sharpen Your Fundamentals with Free Learning

Java Implementation

How Scaler Transformed Careers in Different Fields

₹23L
AVG CTC
SCALER PLACEMENT PROOF

Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.

11,000+placements
650+companies
Verified data
Hiring Partners:
GoogleGoogleAmazonAmazonMicrosoftMicrosoftFlipkartFlipkartAdobeAdobe1200+ more

Python Implementation