Play with friend Complete Solution

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

Transform Your Career

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

+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

+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

+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

+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

Go to Program

Solution Approach

• We'll use the concepts of Grundy numbers and Sprague-Grundy's Theorem in this solution.
• The idea is that every game state can be assigned an integer number, and if there are many elements of a game, then the value assigned to that total game state is the xor of the values of each element individually.
• The Grundy number of a state is the minimum number that is not achieved among any state that the state can move to.
• we have to separate the problem into 2 cases, B even and odd.
• Let f(n) denote the Grundy number of a element of value n. By definition f(0)=0.
• If B is even, then when you split the element of value 2n into B elements of value n, the resulting Grundy number of that state is (f(n) xor'ed n times = 0).
• as B is even. Given this, it is easy to compute that f(0)=0,f(1)=1,f(2)=2,f(3)=0, f(4)=1. Now I will show by induction that for n>=2,f(2n-1)=0,f(2n)=1.
• The case where B is odd is similar but requires more work. Let's look at the splitting operation first. This time, from a element of value 2n we can move to B element of value n, with Grundy number (f(n) xor'ed n times = f(n)) as B is odd.
• So from 2n we can achieve the Grundy numbers f(2n-1) and f(n).

Time Complexity - O(|A|*log(max(A[i])) Space Complexity - O(1)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation