Scaler Topics Fortnightly Contest - 13 Editorial

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

B Distance

You are given an integer array A and an integer B. It is guaranteed that B exists in A at least once. Return another array C of the same size as that of A such that C[i] denotes the distance of the element at the index i to the nearest element in A which is equal to B.

Problem Constraints

• B exists in A at least once.

Input Format

• The first argument is an integer array A and the second and last argument is an integer B.

Output Format

• Return the array C.

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:
The distance of index 1 from nearest B (at index 2) is 1.
The distance of index 2 from nearest B (at index 2) is 0.
The distance of index 3 from nearest B (at index 2) is 1.
The distance of index 4 from nearest B (at index 2) is 2.

Explanation 2:
The distance of index 1 from nearest B (at index 1) is 0.
The distance of index 2 from nearest B (at index 1) is 1.
The distance of index 3 from nearest B (at index 4) is 1.
The distance of index 4 from nearest B (at index 4) is 0.

Hint

• If the current index has B itself, then distance is 0.
• Otherwise, B can present on right to current index, left to current index or both.

Complete Solution

B Distance Complete Solution

Make Beautiful Array

Rupali always pretends to be smart. Once someone asked one question from Rupali. And you as her bestfriend will answer the question to make Rupali happy.

You are given with an array A of distinct integers and you have to make the array beautiful. You can perform any number of operations in the array A. In one operation you can swap any two elements of the array. And the array is beautiful if the cost of the array is minimum and cost of the array is defined as sum of |arr[i-1] - arr[i]| for 1 <= i < |A|.

Now, your task is to find minimum number of operations required to make array A beautiful.

Problem Constraints

Input Format

• Given a array A of distinct integers.

Output Format

• Return an integer denoting the minimum number of operations required to make array A beautiful.

Example

Example Input Input 1:

Example Output
Output 1:

Example Explanation
Explanation 1: In first operation swap A[1] and A[2], now array will be [4, 3, 1, 2]

In second operation swap A[2] and A[3], now array will be [4, 3, 2, 1]

Cost of the array will be |4 - 3| + |3 - 2| + |2 - 1| = 1 + 1 + 1 = 3.

This will be the minimum cost. So the the array is beautiful.
There might be another beautiful array (i.e having same cost).

So, the answer is 2 operations.

Hint

• What will be the cost of array sorted in non-increasing or non-decreasing order?
• Sort the array in ascending and descending order and find the cost for that.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complete Solution

Make Beautiful Array Complete Solution

Sum of GCDs

You are given two integers A and B. Find the Sum of GCDs of all arrays possible of size A consisting of values between 1 and B inclusive modulo $10^9 + 7$.

Problem Constraints

Input Format

• The first argument is an integer A and the second argument is an integer B.

Output Format

• Return an integer denoting the Sum of GCDs of all arrays possible of size A consisting of values between 1 and B inclusive modulo $10^9 + 7$.

Example

Example Input
Input 1:

Input 2:

Example Output
Output 1:

Output 2:

Example Explanation
Explanation 1:
The possible arrays are [1], [2], [3] and [4]. Sum of GCDs = 1 + 2 + 3 + 4 = 10.

Explanation 2:
The possible arrays are [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2] and [3, 3]. Sum of GCDs = 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 3 = 12.

Hint

• If elements of the array range from 1 to B, then, the possible values of GCD can be from 1 to B only.
• For each possible value G (1 <= G <= B), can you find out how many possible arrays (of size A consisting of values between 1 and B inclusive) are there such that their GCD is G.

Complete Solution

Sum of GCDs Complete Solution

Art of Xor

Your friend gives you an integer array A. He also defines a special value of an index as 2i where i is the index(0-based). Then he asks you to select two subarrays of non-zero lengths such that:

The Xor of special values of all indices is equal to the sum of special values of all indices. Note that if an index appears in both subarrays, then it is counted twice in both the Xor value and the sum.
The sum of element-wise xor of these two subarrays is the maximum possible. You are required to return the maximum sum according to the second point.

Please note that for the first requirement, we talk about the special value of indices, while in the second requirement, we talk about the actual elements of the array A.

For example, the sum of element-wise xor of [1 3 5] and [6 4 2] would be 7 + 0 = 7.

Since the answer can be very large, output it modulo $10^9 + 7$

Problem Constraints

Input Format

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

Output Format

• Return a single number according the problem given above.

Example

Example Input
Input 1:

Input 2:

Example Output
Output 1:

Output 2:

Example Explanation
Explanation 1:
Maximum we can get is 5 + 1 = 6

Explanation 2:
One possible solution - First sub-array has [ A[0] ] and second sub-array has [ A[1] A[2] ]. 5 + (3 xor 5) = 5 + 6 = 11

Hint

• The first requirement can be reduced to a very simple thing.
• After that, it can be solved with a nice xor trick.

Complete Solution

Art of Xor Complete Solution