Scaler Topics Fortnightly Contest - 14 Editorial

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

Minimum Number at Position

Alice likes the array very much. She has an array A of integers and she decided to perform exactly one operation on that array of the following type: -

• Choose exactly one element from the array and delete it from the array.
• Append one positive element to the array with a different value than the deleted one.
• Sort the array in non - decreasing order

Now after that, she has to find the minimum element at each position of the array can be.

Problem Constraints

Input Format

• First and the only argument is an integer array A.

Output Format

• Return an array, where each position of the array is the minimum possible element at that position after optimal replacing operation and sorting

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: Alice will delete 4 from array A and append 1 to it. Now, after sorting the array will become [1, 1, 2, 3]. This is the minimum possible array.

Explanation 2: Alice will delete 5 from array A and append 1 to it. Now, after sorting the array will become [1, 2, 3, 4]. This is the minimum possible array.

Hint

• We have to find the minimum number for each position. So, it's better to delete the maximum element of the array and insert the minimum possible element.

Complete Solution

Minimum Number at Position Complete Solution

Maximum Power

You are given an array A. For a subset S of A, $power(S) = |S|*sum(S)$.

Divide A into subsets such that each element of A belongs to exactly one subset and $power(A) is maximum where power(A) = power(S_1) + power(S_2) + power(S_3) + ... + power(S_k)$ where S_1, S_2, S_3, ... , S_k are subsets A is divided into.

Return the maximum possible value of power(A) if you divide A into subsets optimally.

Problem Constraints

Input Format

• The first and only argument is an integer array A.

Output Format

• Return an integer denoting the maximum possible value of power(A) if you divide A into subsets optimally.

Example

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1: You can divide A into {4,0,-1}. Hence, $power(A) = power({4,0,-1}) = 3*(4+0-1) = 9$

Explanation 2: You can divide A into {3} and {5}. Hence, $power(A) = power({3}) + power({-5}) = 1*3 + 1*(-5) = -2$.

Hint

• Let $a>=0$ and $b>=0$.
• $2 * (a+b) >= 1 * a + 1 * b$
• Let a<0 and b<0.
• $2 * (a+b) < 1 * a + 1 * b$

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complete Solution

Maximum Power Complete Solution

Longest Superior Subarray

Popcount(x) denotes the number of 1s in Binary representation of x. An array ARR of length N is called superior if KaTeX parse error: Expected 'EOF', got '%' at position 42: … ... ⊕ ARR[N]) %̲ 2 = 0.

You are given integer array A and Q queries. Queries are given in the form of a 2-D array B of size $Q * 2$. For each query i-

• put $A[B[i][0]] = B[i][1]$

You need to find the length of the longest superior subarray of A after each performing each query. Return an array of size Q denoting the answer for each query in order.

Problem Constraints

Input Format

• The first argument is an integer array A and the second and last argument is a 2-D integer array B.

Output Format

• Return an array of size Q denoting the answer for each query in order.

Example

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1: After performing query 1, A becomes [4, 1, 7]. So, the longest superior subarray is [1, 7] as $popcount(1⊕7) = popcount(6) = 2$.

Explanation 2: After performing query 1, A becomes [1, 1, 3]. So, longest superior subarray is [1, 1, 3] as popcount(1⊕1⊕3) = popcount(3) = 2. After performing query 2, A becomes [1, 1, 2]. So, longest superior subarray is [1, 1] as popcount(1⊕1) = popcount(0) = 0.

Hint

• An array ARR of length N is called superior if KaTeX parse error: Expected 'EOF', got '%' at position 40: … ⊕ … ⊕ ARR[N]) %̲ 2 == 0.
• This is equivalent to saying that the number of elements x such that Popcount(x)%2==1 are even in number in ARR.
• Can you prove this? This simplifies our problem.

Complete Solution

Longest Superior Subarray Complete Solution

Zero Subarray

Given an array of positive integers A. You want to make this array beautiful. An array is considered beautiful if there exists no subarray whose length is equal to the bitwise AND of all elements of the subarray. To achieve this you can do the following operation, select any element of the array and change it to any non-negative integer. Return the minimum number of operations required to make this array beautiful.

Problem Constraints

Input Format

• First and only argument is an integer array A.

Output Format

• Return an integer.

Example

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1: Subarray [1] has length 1 and bitwise AND of all elements also equal to 1. Subarray [2, 3] has length 2 and bitwise AND of all elements also equal to 2. We can change the array [1, 2, 3] -> [4, 5, 3].

Explanation 2: Subarray [1, 2] has length 2 and bitwise AND of all elements also equal to 2. Subarray [2, 3] has length 2 and bitwise AND of all elements also equal to 2. We will change the element at the 2nd index to 4.

Hint

• If we extend any subarray, the length of the subarray will increase, and bitwise AND could remain the same or decrease. Binary Search?

Complete Solution

Zero Subarray Complete Solution