Scaler Topics Fortnightly Contest - 20 Editorial
FREE
DSA Fortnightly - 20 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 20
Permutation Value
You are given the length of the permutation which is A. You have to find a permutation B that maximizes the value of f(B). The value of f(B) is calculated as follows:-
f(B) is initially 1.
- Iterate i from 0 to A-1
- Update f(B) = f(B) * B[i] if f(B)<B[i]
- Update f(B) = 1 if f(B) >= B[i].
Find out a permutation that maximizes the value of f(B) and print the maximum value of f(B).
Problem Constraints
Input Format
- The first integer contains an integer A.
Output Format
- Return an integer denoting the maximum value of f(B).
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: The permutation which maximizes the value of f(B) is [2,1,3,4].
Explanation 2: The permutation which maximizes the value of f(B) is [1,2,3,4,5].
Hint
- Try to think how can you find the maximum value of the permutation.
- Think in terms of greedy approaches.
Complete Solution
Maximum Xor Sum Value
There is an array X of N integers. The array A is the prefix bitwise OR array of X, i.e the value of A[i] = (X[1] | X[2] | .. | X[i]). The array B is the suffix bitwise AND of the array X, i.e, the value of B[i] = (X[i] & X[i+1] & ..& X[N]).
You are given the arrays A and B. Find the maximum possible xor sum value of all the elements of X.
It is guranteed that such an array X always exist.
Problem Constraints
Input Format
- First argument A is an array of integers denoting the prefix OR of X.
- Second argument B is an array of integers denoting the suffix AND of X.
Output Format
- Return an integer, the maximum possible xor sum value of X
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Since A[0] = 0, therefore X[0] must be 0 Since B[2] = 2, therefore X[2] must be 2 Thus, array X should be [0, 3, 2]. The xor sum is 1.
Explanation 2: Since A[0] = 2, therefore X[0] = 2 Since B[1] = 1, therefore X[1] = 1 Therefore, xor sum of X is 3.
Hint
- If any bit is unset in A[i] then all the elements
- X[j] such that j <= i must have that bit unset.
- If any is bit is set in B[i] then all the elements
- X[j] such that j >= i must have that bit set.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Stocks
You are given the prices of a stock for N days. The price on the i-th stock of the day is A[i]. In the beginning, you have 0 stocks and, in the end, you want to own 0 stocks. So, you decided to buy stocks on some days among these N days and sell them within these N days. You also want to maximize your profit at the end of N days. Find the maximum amount of profit you can make in these N days. Also, you can buy atmost one stock daily and sell one stock daily.
Problem Constraints
Input Format
- The first argument contains the array A.
Output Format
- Return an integer denoting the maximum profit you can make in N days.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: You can buy one stock on the first day and sell it on the next day to make a profit of Rs 1.
Explanation 2: You can buy one stock on the first day and sell it on the third day to make a profit of Rs 3.
Turn Learning into Career Growth
Hint
- Think of a optimal data structure which can help you to keep track of the best buying and selling date?
- Think of maintaining the prices in a heapq or priority queue.
Complete Solution
Max Value Substring
You have given a string A of length N. The substring S[l...r] is called good if
- It is palindrome of odd length
- if l -1 >= 0 and r + 1 < N then A[l -1] != A[r + 1] where 0 <= l, r < N
There can be multiple good substrings which have the same length X is number of good substring which has length equal to Y The score is defined as X multiplied by the number of set bits present in the binary representation of Y. Your task is to find the maximum score among all pair {X, Y}
Problem Constraints
Input Format
- First argument contains the String A.
Output Format
- Return the maximum score
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: There are total of 4( A(0,0), A(4, 4), A(5, 5), A(6, 6) ) good substring of length 1 and there are total of 1 set bit persent in 4 so our ans will be 4 * 1 = 4 and this will be the optimal answer We can also get score 4 by taking X = 2 and Y = 3
Explanation 2: There are total of 2( A(0,0), A(1, 1)) good substring of length 1 and there are total of 1 set bit persent in 1 so our ans will be 2 * 1 = 2 and this will be the optimal answer
Hint
- Try to use the properties that Whenever A(l,r) is palindrome then A(l+1,r-1) is also palindrome
