Scaler Topics Fortnightly Contest - 15 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 15
Missing XOR
Initially, you had all integers from 1 to A, but you lost a pair of integers among them and now you only know the XOR of the remaining A-2 integers which is B. Find the count of different possible pairs which you could've lost.
Problem Constraints
Input Format
- The first argument is the integer A.
- The second argument is the integer B.
Output Format
- Return a single integer which is the count of different possible pairs which you could've lost.
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:
Initially we have {1, 2, 3}.
If we remove {1, 2} the xor of remaining elements would be 3.
Similarly, by removing {2, 3} we get 1, and by removing {1, 3} we get 2.
So only 1 pair satisfies the required condition.
Explanation 2: Pairs satisfying the condition are {2, 3} and {4, 5}. It can be checked no other pair would satisfy the required condition.
Hint
- What would be the xor of the lost pair?
Complete Solution
Count Single Value
You have to create the array D and then find the valid element in the array according to the below queries. There are three types of query
- 1, x, -1: add x into the array D
- 2, x, -1: remove one occurrence of x if it present in an array D
- 3, x, y: you have to find all values B and C from array D which satisfy the below conditions and return their absolute difference (abs(B - C))
For B: create an special element z which is equals to the sum of all 2i values that satisfy the condition & 2i ) > 0KaTeX parse error: Expected 'EOF', got '&' at position 42: … z where ^ and &̲ represents Bit…((B^y)$ & 2i ) > 0 where 0 <= i <= 28 and x < z where ^ and & represents Bitwise XOR and Bitwise AND operations respectively It is guaranteed that type 3 query occurs at most 10 times You are given queries in the form of 2D array A of 3*C length A[i][2] = -1 for 1st and 2nd type of query
Problem Constraints
Input Format
- First argument A is an 2D array of integer that contains all the queries.
Output Format
- Return an array of integer that contains output of all type 3 query.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1:
after 1st query D = [4]
after 2nd query D = [4, 4]
after 3rd query ans = 2(B = 2, C = 0)
after 4th query D = [4]
after 5th query ans = 1(B =1, C = 0)
Explanation 2: There are no qurery of type 3 so we will return empty array.
Hint
- Think of some brute force approaches as the given constraints are not too big
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
Hot Summer Giveaways
The mentors of Scaler Academy are one of the best in the world. This hot summer they decided to gift cool water bottles to all their students. There are N students in a class. The drinking water capacity of all the students in the class is given by an array A.
The only problem is that we can gift these N bottles of the same size.The dissatisfaction level of a student is defined as the square difference between his drinking capacity(A[i]) and the capacity of the water bottle gifted to him(X).
You have to determine the minimum size of bottle that should be purchased which minimizes the total dissatisfaction among the students.
In other words, you have to minimize the value of = .
Problem Constraints
Input Format
- The first and only argument is array A.
Output Format
- Return an integer, denoting the minimum size of water bottle that is needed to minimize the total dissatisfaction of all the students.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1:
Total dissatisfaction value that is achieved using bottle capacity of 8 is, 0+2+3+1+7 = 13. We can see that is the minimum we can achieve.
Explanation 2: Here, total dissatisfaction value that is achieved using bottle capacity of 6 is, 10+8+3+2+0+3 = 26. We can see that is the minimum we can achieve.
Turn Learning into Career Growth
Hint
- Let us suppose the optimal size of the bottle is x. Then for all the size of bottles greater than x, and less than x, we will acheive greater dissatisfaction, than what is achieved at size x.
- Does this give any hint about some approach we can use here?
Complete Solution
Divisible Magical Numbers
Naaya and Haytham were two friends, they have completed their class assignments and asked their maths teacher for a problem to solve. Their maths teacher gave them a string of digits A of size N, and gave Naaya an integer B and Haytham an integer C.
She asked them to traverse the string of digits from left to right (i from 0 to N - 1) and asked either Naaya or Haytham to append the digit to the end of their magical number with mutual coordination. Initially, both of them have an empty magical number.
Their maths teacher wants the following points to be satisfied.
- Each digit present in string A must belong to either Naaya or Haytham, but not both.
- Both Naaya and Haytham must have at least 1 digit in their magical numbers.
- Naaya’s magical number must be divisible by B.
- Haytham’s magical number must be divisible by C.
Let the number of digits present in the Naaya’s magical number be x and Haytham’s be y. Their maths teacher wants the absolute difference between x and y to be minimum. (|x - y| to be the minimum possible).
She wants them to return a string of size N of letters ‘N’ or ‘H’, where ‘N’ denotes the ith digit from string A is taken by Naaya and ‘H’ denotes it is taken by Haytham. If there are multiple answers, return the lexicographically largest string.
If it is not possible to create the string by following the above points, return “INVALID”.
Note: Ignore the leading zeroes, if the magical number is 0012, it will be treated as 12 but the number of digits is still 4.
Problem Constraints
Input Format
- The first argument is a string A.
- The second argument is an integer B.
- The second argument is an integer C.
Output Format
- Return a string of size N if it is possible to create a valid string, else return "INVALID".
Example
Example Input
Input 1:
Input 2:
Input 3:
Example Output
Output 1:
Output 2:
Output 3:
Example Explanation
Explanation 1:
Let x be the length of Naaya Magical number, and y be the length of Haytham Magical number.
The minimum possible value of |x - y| is zero which can only be formed by "HNNH" where magical numbers of Naaya and Haytham are"39" and "70" respectively.
Explanation 2: It is impossible to distribute the digits among them which satisfies all the conditions. Hence, we return "INVALID" as answer.
Explanation 3: Let x be the length of Naaya Magical number, and y be the length of Haytham Magical number. The minimum possible value of |x - y| is zero which can only be formed by {"HNNH", "HHNN", "NNHH", "HNHN", "NHHN", "NHNH"} The lexicographically largest string among them is "NNHH", where magical numbers of Naaya and Haytham are "00" and "00" respectively.
Hint
- The number x is divisible by the number y if and only if x%y == 0.
- We can see that the value of |A|, B and C is at most 50, can we use the concept of dynamic programming to solve the problem.
