Scaler Topics Fortnightly Contest - 1 Editorial

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

Magic School

Harry and his friends are students of a famous magic school. Unfortunately, they've scored very less marks in a test and want to use magic to increase their marks so that everyone's marks become equal to the initial maximum.

You are given an array A containing the marks of every student and a magic number B. Each magic operation can increase the marks of any student by exactly B points. Find out if B is a correct magic number to equalize everyone's marks using some number(possibly zero) of magic operations. Return 1 if it is and 0 if it is not.

Problem Constraints

Input Format

• The first argument is the integer array A.
• Seond argument is the integer B.

Output Format

• Return a single integer as per the given problem

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

Example

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1: Do the magic operation 4 times for A[0], 3 times for A[1], 2 times for A[2], and 1 time for A[3] to equalize everyone's marks

Explanation 2: 0 magic operations are needed to equalize everyone's marks. Hence, the answer is 1.

Hint

Think about what condition must hold such that B becomes a correct magic number.

Can something be done with the difference of max with every value?

Complete Solution

Magic School Complete Solution

Minimum Cost Tree

You're given N nodes, every node has some weight Ai.
You want to make a tree out of these N nodes but there is some cost of joining two nodes. The cost of adding an edge between two nodes X and Y is Cost(X) + Cost(Y).
The Cost(K) function gives the sum of weights of all nodes that are currently reachable from K including K.
Find the minimum cost for making the tree.

Problem Constraints

Input Format

• First argument A is an integer array.

Output Format

• Return an integer.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation

Explanation 1:
The cost of joining node 1 and 2 is 1 + 1 = 2
The cost of joining node 2 and 3 is 2 + 1 = 3. Total cost = 2 + 3 = 5.

Explanation 2:
The cost of joining node 1 and 2 is 1 + 2 = 3
The cost of joining node 2 and 3 is 3 + 3 = 6
Total cost = 3 + 6 = 9.

Hint

Joining two nodes with samllest Cost(K) value such that both are not reachable from each other is best option.

Complete Solution

Minimum Cost Tree Complete Solution

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Triangular Sum

You are given a positive integer A. Can A be represented as sum of triangular numbers ? If yes then return minimim number of triangular numbers required to represent A or else return -1.

Triangular numbers are the numbers of the form $N*(N+1)/2 whre 1 <= N$.

Problem Constraints

Input Format

• First argument contains a number A.

Output Format

• Return the minimum number of triangular numbers required to represent A else return -1.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: 6 is a triangular number.

Explanation 2: 10201 can be represented as 5050 + 5151

Hint

After carefully looking at the definition of triangular numbers we can see that every number can be represented as the sum of three triangular numbers. Check whether it can be done with one or two triangular numbers.

Complete Solution

Triangular Sum Complete Solution

Bob and Assignments

Bob's current semester is coming to an end and he is given N assignments numbered from 1 to N to complete to pass the semester.These assignments are from B subjects numbered from 1 to B .
Bob will do these assignment in numerical order over multiple days. Bob will do atleast one assignment each day till he have no assignments left to do.
Also Bob can do more than one assignments the same day but he doesn't want to do more than one assignments from same subject on the same day.
Bob wants to know in how many ways he can complete these assignments under these conditions.
Two ways are different if the number and type of assignment done on any day is not equal.

Given an integer array A , where $1 <= A[i] <= B$ referring i'th assignment belongs to A[i] subject and an integer B return the total number of ways modulo 1000000007.

Problem Constraints

Input Format

• The first input is an integer array A.
• The second input in an integer B.

Output Format

• Return an integer modulo 1000000007.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: Following are the five ways bob can complete the assignments:

[{1}, {2}, {1}, {2}, {2}]
[{1, 2}, {1}, {2}, {2}]
[{1, 2}, {1, 2}, {2}]
[{1}, {2,1}, {2}, {2}]
[{1}, {2}, {1, 2}, {2}]

Hint

Try to find the overlapping solutions.

Complete Solution

Bob and Assignments Complete Solution