Scaler
Academy
Data Science
AI/ML
DevOps
Neovarsity
AI FDE Program
IITR Degree Program
New
Skill Test
Search for Articles, Topics
Scaler Topics Fortnightly Contest - 16 Editorial

Scaler Topics Fortnightly Contest - 16 Editorial

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Start Learning View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

DSA Fortnightly - 16 Editorial

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

Water Supply

There are N taps in the city, which are connected such that if one tap is opened then all other taps will also automatically get open.

Now, you are given two integers A and B and an integer array C.

  • A - Total amount of water poured out from all taps.
  • B - The amount of water that needs to be poured out from the last tap.
  • C - The outgoing hole size of each tap.

Now, you can block the holes of some taps so, that no water comes out from them. Now, the amount of water that comes out from each tap is directly proportional to the size of the hole of that tap. Like if the sum of the size of all tap holes which are open is X. Then the amount of water that comes out from each open tap will be (C[i]*A)/X.

Now, your task is to find the minimum number of tapes whose holes you have to close so that amount of water that came out from the last tap is at least B.

Problem Constraints

1<=B<=A<=1041<=∣C∣<=1051<=C[i]<=104\begin{aligned} 1 <= B <= A <= 10^4\\ 1 <= |C| <= 10^5\\ 1 <= C[i] <= 10^4\\ \end{aligned}

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.

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
GoogleAmazonPaytm+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
GoogleAmazonPaytm+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
GoogleAmazonPaytm+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
GoogleAmazonPaytm+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
Program highlights
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
GoogleAmazonPaytm+1000 more
Go to Program

Example

Example Input
Input 1:

Input 2:

Example Output
Output 1:

Output 2:

Example Explanation
Explanation 1: Total amount of water poured from all taps is 10 and that has to come all out from last tap. So, we have to close all other tap.

Explanation 2: Total amount of water poured from all taps is 80 and out of that atleast 20 has to come out from last tap. So, according to the formula given in problem if no tap hole is closed then. Water that came out from first tap will be (480)/10 = 32 Water that came out from second tap will be (180)/10 = 8 Water that came out from third tap will be (280)/10 = 16 Water that came out from fourth tap will be (380)/10 = 24 So, no need to close outgoing hole of any tap.

Hint

  • It is clear that we have to block taps with greater outgoing hole first.
  • So, we can sort the array C, excluding the last element because we have to keep that open.

Complete Solution

Water Supply at Position Complete Solution

Maximum Sweetness

There are A number of students in a class and one of them is the representative of the class. A class representative has a bag of A chocolates where the sweetness of the ith chocolate is i (starting from 1).

He can choose atmost B chocolates from a bag of A chocolates to maximize the sweetness and here sweetness is not defined as the sum of the sweetness of chosen chocolates, it will be the XNOR of the sweetness of all the chocolates chosen. So, you have to output the maximum sweetness class representative can get.

Note - While calculating XNOR of two numbers X and Y, remember that you have to take XNOR only till the last set bit encountered in the largest integer of X and Y.

Example - if two integers are 5(101) and 2(10). Then their XNOR will be 0(000). The larger of 5 and 2 is 5 and the largest set bit in 5 is 4

Problem Constraints

1<=A<=1091<=B<=A\begin{aligned} 1 <= A <= 10^9\\ 1 <= B <= A\\ \end{aligned}

Input Format

  • First argument is an integer A, which represents number of chocolates in bag.
  • Second argument is an integer B, which represents maximum number of chocolates class representative can choose.
Sharpen Your Fundamentals with Free Learning

Output Format

  • Return an integer C, which represents maximum sweetness representative can get.

Example

Example Input
Input 1:

Input 2:

Example Output
Output 1:

Output 2:

Example Explanation
Explanation 1: Class representative can take chocolates from type 1 to 10 and atmost 2 chocolates type he can choose. But the maximum XNOR he will get by taking out chocolate of type 8 and 9 as their binary representation is 1000 and 1001 resepectively which will give XNOR as 14(1110). And in all other cases XNOR value will be either less than or equal to 14.

Explanation 2: Class representative can take a maximum of 3 types, He will take only chocolate of type 7 as this will give maximum XNOR value. Selecting more than one will not be the optimal choice here as that will never give more than 7 value
because in binary representation of 7 - (111) all bits are set and it is the largest type here.

Hint

  • What would be the maximum sweetness if B = 1?
  • What will be maximum sweetness if A=1 or A=2?

How Scaler Transformed Careers in Different Fields

₹23L
AVG CTC
SCALER PLACEMENT PROOF

Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.

11,000+placements
650+companies
Verified data
Hiring Partners:
GoogleGoogleAmazonAmazonMicrosoftMicrosoftFlipkartFlipkartAdobeAdobe1200+ more

Complete Solution

Maximum Sweetness Complete Solution

Good Number

You are given an integer A. You have to find the minimum good number not less than A. A good number is a positive number which has the same difference between the adjacent digits.

Problem Constraints

1<=T<=101<=A<=109\begin{aligned} 1 <= T <= 10\\ 1 <= A <= 10^9\\ \end{aligned}

Input Format

  • The first argument contains the integer A.

Output Format

  • Return a single integer denoting the maximum number not less than A.

Example

Example Input
Input 1:

Input 2:

Example Output
Output 1:

Output 2:

Example Explanation
Explanation 1: The nearest good number to 157 is 159 as 5-1=9-5.

Explanation 2: The nearest good number to 8 is 8.

Turn Learning into Career Growth

1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary
1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary

Hint

  • Try brute forcing the solution.
  • There are not many good numbers present, so explore all of them.

Complete Solution

Good Number Complete Solution

XOR Subsequence

You are given an integer array A and an integer B. Return 1 if there exists a subsequence of this array such that XOR of all elements in the subsequence equals B else, return 0.

Problem Constraints

1<=∣A∣<=321<=Ai<=1090<=B<=109\begin{aligned} 1 <= |A| <= 32\\ 1 <= Ai <= 10^9\\ 0 <= B <= 10^9\\ \end{aligned}

Input Format

  • The first argument is an integer array A.
  • The 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: We can take the subsequence [1, 9] as (1^9) = 8.

Explanation 2: There is no subsequence whose XOR equals 4.

Hint

  • Think of dividing the arrays in two parts.
  • Then use some property of xor.

Complete Solution

XOR Subsequence Complete Solution