Solution 4 for Scaler Topics Fortnightly Contest - 1

This article is part of the Scaler Topics Fortnightly Contest - 1.

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

+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

NSDC Certified

AI Forward Deployed Engineer Program

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

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

• This problem can be solved using dynamic programming. Set dp[i] = the number of combinations that take up to the i-th supplement at the end of a day. If we ignore the condition that we cannot do more than one assignment from the same subject then the recurrence relation will be, $dp[i] = dp[i-1]*2$
• Now we will use an array or hashmap p to store the last index the same subject assignment appeared. Now we will use this to subtract the i’th day ways. $dp[i] = dp[i] - dp[p[A[i]]]$
• Now to find the total number of ways for the i’th day $ans = dp[N] - dp[N-1]$
• Do not forget to do mod 1000000007 to avoid overflow. Time Complexity O(N) Space Complexity O(N + M)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation