Solution 3 for Scaler Topics Fortnightly Contest - 11

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

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

• Assume the given array C is a binary number. Now see that the constraints are just upto 24. So try to come up with an idea using bitmasking.
• We will solve the problem using recursion bitmasking and dp memoization.
• Assume the given array C is the initial state as a binary number.
• First convert that number to decimal say x and initialise dp[x] = no of set bits in x.
• Then recursively call the reachable states say y from this number and dp[x] = min(dp[x], find(y)).
• Then return dp.Remember to use memoisation that is if we had already called a state before
• we must have the answer for that state saved. Use that. Or it will take a lot of time.
• Using memoization we will avoid repeated recursive calls of a reachable states which will bring down
• the complexity from $O(N * 2^N)$. Also skipping unreachable states will also bring down the complexity to a much lower one. So although it might look like the worst case complexity is $O(N * 2^N)$.
• If implemented better it will reduce to a much lower one.
• For example - Take the example case A = 4
  B = 6
  C = [1, 1, 1, 0, 1, 0]
  If we try to reach all the states then total number of states is $6 * 2^6 = 384$. If we traverse to only the reachable states then there are only 4 reachable states as follows. [1, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 0], [1, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 1].
• Check implementation for more details.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation