Scaler Topics Fortnightly Contest - 4 Editorial

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

AND Subsequence

Given an integer array A. Find the length of the largest subsequence such that bitwise and of all elements in it is not less than B.

Problem Constraints

Input Format

• First argument is an integer array A.
• Second argument is an integer B.

Output Format

• Return an integer.

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: We can take the subsequence [2, 3].

Explanation 2: There is no valid subsequence such that and of all elements is not less than 4.

Hint

• Think bitwise.
• We can select elements in some greedy way such that our bitwise and does not go below B.

Complete Solution

AND Subsequence Complete Solution

Maximum Xor Sum

You are given an array A of length N. You can select two non intersecting subarrays of length B at max, and xor all the elements in a subarray and then sum the resultant xor. Find the maximum sum which you can obtain.

Problem Constraints

Input Format

• First argument is an integer array A.
• Second argument is an integer B.

Output Format

• Return an integer.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: The two subarrays will be [1, 2] and [3] $(1^2) + (3) = 6$

Explanation 2: The two subarrays will be [3, 4] and [5] $(3^4) + (5) = 12$

Hint

• We can find the xor of all the subarrays.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complete Solution

Maximum Xor Sum Complete Solution

Equalise sinks

You are the chef of a very popular restaurant and it becomes very messy so you decide to clean it up!

In front of you there are A sinks and each sink contains some used plates given by array B, B[i] denotes plates in i'th sink. To divide the work load equally you want to rearrange plates such that every sink has equal ammout of plates. (It is given that it will always be possible.) In one move you can carry one plate to its adjacent sink. Determine minimum number of moves required to equalise the sinks.

Note: It is given that answer will fit in a 32 bit signed integer for given test cases.

Problem Constraints

Input Format

• First argument is A number of sinks.
• Second argument is B array for number of plates in each sink.

Output Format

• Return an integer, mimimum number of moves required.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: Move 3 plates from index (1-based) 4 to 3 and 1 plate from index 2 to 3, using 3+1 moves. then array becomes [8, 0, 4, 4]. Then move 4 plates from index 1 to 2, using 4 moves. Final array would look like [4, 4, 4, 4] and total number of moves will be 8.

Explanation 2: Finaly array looks like [2, 2, 2], it is fairly simple to see that 4 moves are required.

Hint

• Finally what will be the number of plates per sink?
• If you were working in real life what strategy you would have followed?
• You would have been greedy while carrying the plates.
• If you are at sink i, can you calculate how many plates would cross sink i?

Complete Solution

Equalise sinks Complete Solution

Magical Path

You are the great magician Harry, and on your way to home. You are in a country consisting of A cities numbered from 1 to A. You are at city 1 and your home is in city A.

The cities are internconnected by M bidirectional road, such that it is possible to reach any city from any other city. The roads are represented by matrix B, where B[i][0] and B[i][1] represents the cities which are connected by the ith road, and B[i][2] represents the time required to travel through this road. No two cities are directly connected by more than one road. You wish to reach you home in city A spending the minimum possible time.

You also have supplies of infinite good and bad magic potions. Using a good magic potion you can reduce the time required to travel a road to 0 but you also have to spend C amount of time on using it, and using a bad magic potion you double the time required to travel a road.

You can use 0 (zero) or more magic potions as required.

Following are the conditions on the usage of magic potion:

1. You have to travel through the road on which you have used a magic potion, i.e., if you have used a magic potion on a road, that road must exist in your path from city 1 to city A.
2. You cannot use two or more good magic potions consequently.
3. You cannot use two or more bad magic potions consequently.
4. You have to use equal number of good and bad magic potions.
5. The very first magic potion used should be a good magic potion.
6. You cannot use more than 1 magic potion on a particular road.
7. You have to spend C amount of time on using a good magic potion.
8. You have to spend 0 (zero) amount of time on using a bad magic potion.

Problem Constraints

Input Format

• First argument A is the number of cities.
• Second argument B is the matrix representing the roads. B[i][0] and B[i][1] represents the cities connected by the ith road, and B[i][2] represents the time required to travel through the ith road.
• Third argument C is the time required while using a good magic potion.

Output Format

• Return the minimum time required to reach Ath city from 1st city, while using as many good/bad magic potions required (following the rules mentioned in the problem statement)

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: The optimal path consists of the following cities in the corresponding order: 1 -> 2 -> 4 -> 5 On the road 1 -> 2, we use a good magic potion. On the road 4 -> 5, we use a bad magic potion.

Explanation 2: The optimal path consists of the following cities in the corresponding order: 1 -> 3 -> 5 We are not using any magic potion here.

Hint

• The parity of the number of potions used at the end should be 0. Can we use this information?
• You need to find the minimum time required, can you think of any graph algorithm related to this? Dijktras?

Complete Solution

Magical Path Complete Solution