Scaler Topics Fortnightly Contest - 6 Editorial

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

Counting Special Arrays

A number is nice if it is divisible by 4. Given an array A of size N and an integer B, you need to count the number of special sub-arrays in the array. A continuous sub-array is called special if it has B nice numbers.

Problem Constraints

Input Format

• First input argument contains an integer array A.
• Second input argument contains an integer B.

Output Format

• Return the count of number of special sub-arrays.

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

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: There are only 2 subarrays which have 3 nice numbers. [4, 8, 10, 12 ] , [8, 10 , 12 , 16].

Explanation 2: There is no nice number in the array. So there is no sub-array which has 1 nice number.

Hint

• Instead of finding sub-arrays having B nice numbers
• Try finding sub-arrays which have at Most B nice numbers (i.e 0 to B). Will it help ?

Complete Solution

Count Special Arrays Complete Solution

Minimum Energy Drinks

You are standing at origin and fighting some monsters in your way to rescue your friend. Monsters are present along the positive x axis, their positions and strengths are given by arrays A and B respectively.

A[i] denotes the x coordinate and B[i] denotes the minimum energy required to kill i'th monster. Thankfully, there are some energy drinks on the way to rescue. The positions of energy drinks and amount of energy provided by them are given by arrays C and D respectively. i'th energy drink will increase your energy by D[i] units. You know that your friend is at position E, to reach him you need to kill all the monster between you and him. Initially your energy is F.

What is the minimum number of energy drinks you need to take? If it is not possible to rescue your friend return -1.

Problem Constraints

Input Format

• First argument is an integer array A, denoting the position of monsters.
• Second argument is an integer array B, denoting the minimum energy required to kill monster.
• Third argument is an integer array C, denoting the position of energy drinks.
• Fourth argument is an integer array D, denoting the amount of energy increased by energy drink.
• Fifth argument is an integer E, position of your friend.
• Sixth argument is an interger F, initial energy.

Output Format

• Return the minimum energy drinks required to reach your friend else return -1.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1:

You don't have enough energy to destroy the first monster in your way.

Explanation 2: You can destroy the first monster and pickup the energy drink at x - coordinate 2 to make your energy 15 and then destroy the second monster and reach 4.

Hint

• Should we sort the monsters and energy drinks according to their x - coordinate?
• Can you think of a greedy approach?
• If you are not able to reach to the destination which energy drink you should try to consume?
• You should try to consume the energy drink which gives you the maximum energy so far, as only number of drinks matter.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complete Solution

Minimum Energy Drinks Complete Solution

Super Mario

You are playing the new Super Mario game. The game is in the form of a matrix of dimensions A×B. The matrix cells are represented by their row and column number (i, j).

Initially, Mario is at cell (1, 1) and wants to rescue Princess Peach, who is at cell (A, B). Mario can make the following types of moves if possible in the matrix form cell (i, j) go to (i+1, j), (i+2, j), (i, j+1), (i, j+2).

Also, there is a teleportation tower in each row, from tower of rowi Mario can go to the tower of rowx if x > i.

The location of towers is given by an integer array C, where Ci represents the column number of the tower in the ith row.

Also, Mario can not do the same type of move consecutively. Return the number of ways to reach Princess Peach's cell, since the answer can be large return it modulo $10^9+7$.

Problem Constraints

Input Format

• The first argument is an integer A.
• The second argument is an integer B.
• The third argument is an integer array C.

Output Format

• Return an integer.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: (1, 1) -> (1, 2) -> (2, 2) (1, 1) -> (2, 1) -> (2, 2) (1, 1) -> (2, 2) here we used teleporation tower of cell (1, 1) to reach teleporation tower of cell (2, 2).

Explanation 1: (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) (1, 1) -> (2, 1) -> (2, 3) (1, 1) -> (1, 3) -> (2, 3) (1, 1) -> (2, 2) -> (2, 3) here we used teleporation tower of cell (1, 1) to reach teleporation tower of cell (2, 2).

Hint

• We can use Dynamic Programming here to solve this problem, as we have reached some cell we only care about the last move used to reach this cell.

Complete Solution

Super Mario Complete Solution

Chaotic Kingdom

There is a very peaceful kingdom with A cities which are connected with B bidirectional roads. It is possible to reach any city from any other city using some of the roads.

In each city there are some people living in it. C[i] is the population of i'th city. The roads are given by a 2D array D, denoting D[i][0] is connected to D[i][1]. There is exactly one road between any particular pair of cities.

During a war enemies try to create a chaos and destroy exactly one of the roads such that the kingdom is divided into two parts. The order of chaos can be measured as product of population of the two parts. What is the maximum chaos enemies can cause? If it is not possible for enemies to cause the chaos return -1.

Problem Constraints

Input Format

• First argument A is number of cities in the kingdom
• Second argument B is number of roads in the kingdom
• Third argument C is an array denoting population of each city
• Fourth argument D is a 2D array denoting roads.

Output Format

• Return a single integer the maximum chaos if possible else -1.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: Destroying any of the roads does not divide the kingdom in two parts. Therefore -1 is the answer.

Explanation 2: Both the roads divide the kingdom in two parts. Product of populations on breaking the roads are 30 and 12 respectively.

Hint

• Brute force approach would be to remove each edge and calculate the required product?
• Can you do better?
• What type of roads would divide the kingdom into two parts?
• Prerequisite: Bridges in the graphs. Can you use this concept with some preprocessing?

Complete Solution

Chaotic Kingdom Complete Solution