Solution 1 for Scaler Topics Fortnightly Contest - 12
FREE
This article is part of the Scaler Topics Fortnightly Contest - 12
Build an AI-First Career, Master the Complete Skillset
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
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreSolution Approach
- Let denotes count of 'A's and denote count of 'B's
- Now, consider 3 cases:
-
Alice can't make any moves, so the game ends at the very first move, with a draw.
-
Whatever move Alice makes, she can't gain any point. So, the result would either be lose or draw.
-
and An optimal move for Alice is to choose all the 'A's as her subsequence in 1st move and gain point equal to count_B. Now, whatever move Bob plays, he can't gain any point, as all 'A's are removed.
- Alice would win in this case.
Time complexity:
Space complexity:
C++ Implementation
Java Implementation
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
