Scaler Topics Fortnightly Contest - 2 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 2.
Making new friends
You want to make new friends. You have a list of peoples with their qualities. Quality of a player is given in the form of a integer. Consider binary represetation of that integer, if the ith bit is 1, then the person have that quality, otherwize he doesnot have it. You want to be friends with someone having more opposite qualities. You want to be friends with a person if number of qualities on which you two differ is greater than C. How many friends will you be able to make ?
Problem Constraints
Input Format
- First line is an integer A. Representing your quality.
- Second line an integer array. Representing the qualities of people you want to be friends with.
- Third line is an integer C.
Output Format
- Return an Integer, equal to number to people you can be friends with.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: Binary representation of 2 is 010 , and of 5 is 101 , number of bits they differ are 3, there are two fives hence answer is 2.
Explanation 2: Binary representation of each number is : 101 , [ 010, 001, 011 ] , only 101 and 010 differ on more than 2 bits hence answer is 1.
Hint
For counting number of bits on which two numbers differ, you can do xor of two numbers and then count the number of bits of result number.
Complete Solution
Transmit the signal
There are A stations placed on the boundary of a circle and one in the center of the circle. The central station is connected to every other station. whereas, all boundary stations are connected to the immediate left and the immediate right stations. Whenever a station wants to broadcast a message it sends it to one (only one out of 3) of the connected station which does not have the message already.
You have to tell the total number of ways in which a message can be broadcasted such that it reach all the stations.
Problem Constraints
Input Format
- First and only argument is an Integer A.
Output Format
- Return a integer denoting number of ways to transmit message.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: All permution of paths are valid in this case.
Explanation 2: Considering 5 as central node and 1-4 at boundary, Few of the Invalid path: { 1, 3, 2, 4, 5} , {1, 5, 2, 5, 3, 4,}
Hint
First try the brute force approach using backtracking. Now can you make an observation about what type of path on what type of graph it is asking. Do we have a generalised answer for that?
Complete Solution
Subsequences
You are given two strings A and B. Consider all the subsequences of A which are equal to B. Lets mark the characters of these subsequences of A to be visited. Are all the characters of A visited? In other words, can each character of A be a part of some subsequence of A, which is equal to B.
Problem Constraints
Input Format
- First line is string A.
- Second line is string B.
Output Format
- Return "Yes" if all characters of A are visited otherwise return "No".
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: All the characters of string A can be used to form a subsequence which is equal to string B. Hence answer is Yes.
Explanation 2: String A contains 'b' which can not be visited. Hence answer is No.
Hint
- Let n be length of A.
- Let m be length of B.
- Lets say for ith position in string A, L[i] is the largest integer such that string B0...L[i] is present as a subsequence in A0..i .
- Similarly for ith position in string A, R[i] is the smallest integer such that string BR[i]...m-1 is present as a subsequence is Ai..n-1.
- What do you observe position these two informations about an index?
Complete Solution
Sorting via reversing
You are given an array of strings. You have to sort this array of strings in lexicographical order. But you can apply only the following operation : Reverse a string. You cannot change the order of strings. A[i] will be the cost of reversing the ith string. Determine the minimum amount of energy you have to spend to sort the strings. If you cannot sort the strings then return -1.
Problem Constraints
Input Format
- First line is an integer array A, where the A[i] denotes the cost to reverse ith string.
- Second line is the string array, which you have to sort.
Output Format
- Return the minimum cost to sort the string array, otherwise return -1 if you cannot sort the array.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: You have to reverse the first string to make to array sorted.
Explanation 2: You dont have to do anything, array is already sorted.
Hint
As the problem has overlapping subproblems, dynamic programming can be applied here.