Join Us
Loading Similar Posts
Entering edit mode
Question 3
Overview
- Given an integer number we have to check if the number is odd or even and perform the operation based on that
- If the number is odd then print the value of the product of that number for example 113 then the product is 113=3
- if the number is even then print the value of the sum of the number for example 112 then the sum is 1+1+2=4
Solution
- We are given an integer value that is also less than 10^8 so the answer for that problem can be divided into two sub problem
- First for odd we can create a function that will convert we can do this easily by recursion for using for loop if we consider the highest value also that is going to be 10^8-1 then also product of the number can easily be fitted within the long data type. -The second case when the given number is even then we can simply use for loop and add every element of the given integer this can be easily done by taking N as input as a string and after that iterating threw string and converting each character to an integer by stoi() function in c++.
Entering edit mode
Question 2: Alex Keyboard
Overview
- Determine the number of strings which when typed using this keyboard, may produce the given strings.
Approach
Scan the string from left to right.
Keep track of "lengths of chains"
e.g. aabbbbbcddd - it has chain of a's of length 2, chain of b's of length 5, chain of c's of length 1, chain of d's of length 3
Answer is product of length of all such chains 2 x 5 x 1 x 3 = 30
just keep performing modulus while doing the multiplications.
Complexity
Time Complexity: O(|S|) |S| is size of the string.
Entering edit mode
Question 1
Overview
Given two string S and T, determine if S can be shuffled in such a way that T does not occur as a subsequence of S.
Approach
- This problem can be broken into some cases
- There can be only one "NO" case, where if T contains only one letter repeated multiple times, and S contains at least those many letters, the answer will always be 'NO'.
- Else, the answer will always be "YES"
- If S doesn't contain some character in T (S doesn't contains 'c' and T contains 'c' or S contains 3 'c' but T contains 4 'c'), T can never occur as a subsequence, and hence answer will be "YES".
- Else, sort S. If T is already in sorted order, reverse sort S. This will always give S s.t T never occurs as a subsequence.
C++ Code
bool solve(string s,string t)
{
map<char,int> sm,tm;
for(auto c:s)
sm[c]++;
for(auto c:t)
tm[c]++;
if((int)tm.size()==1)
{
for(auto x:tm)
{
if(sm[x.first]>=x.second)
return false;
}
}
return true;
}
Time Complexity: O(|S|+|T|)
