Join Us
Loading Similar Posts
Entering edit mode
Kitty in horror house
A Kitty is locked inside a horror house. There are distinct random words written on the wall. Kitty met a ghost inside the house. Ghost offered to help, but
on one condition, he said "I will give you a word. you need to tell if you can create this word using the words written on the walls of the horror house. If
you are correct, I'll take you out of the house else you are stuck here forever". You need to write an
algorithm which can help the Kitty. You need to return true if yes else return false.
Note: The same word in the dictionary can be reused multiple times in the segmentation or not.
Example 1
Input:
s = "hackerrank"
wordDict = ['"hacker", "rank"]
Output:
trueConstraints
• 1 <= s.length <= 300
<- wordDict. length <= 1000
= wordDict.length == 20
s and wordDictli] consist of lowercase English letter only
• 1 <= n <= 50
-1000 <= grid[i] <= 1000
• 0 <= k <= 1000
Optimum Oxygen Level
Ahter defeating Dr. Eggman, Sonic the Hedgehog has Finally returned to the Green Hill Zone. The forest critters make him the de facto king of the Hill for his
victory. But unfortunately a new, more demanding problem awaits him: the oxygen levels in the Zone are now unstable and he has to evacuate all of his
subjects to a safe area as soon as possible. Green Hill Zone is linear in geography and all the neighbourhoods in it are on a straight line. Each
neighbourhood in Green Hill Zone has an oxygen value assigned to it denoted by O. The oxygen value of a range of neighbourhoods I -+ r (both L and r inclusive) is calculated by the following equation
derived by Tails the Fox:
Simply put, it is the bitwise AND of all the O values between both land r. To decide which neighbourhood or range of
neighbourhoods is safe, Sonic has given a safe target oxygen value T to Tails.
Help Tails prepare the safest range of neighbourhoods by finding the minimum possible
value of O[l,r] - TI where I <= r.
Input Format
The first line contains N which is the number of neighbourhoods in Green Hill Zone
The next M lines contain N integers denoting the oxygen level O, for each neighbourhood The last line contains T the target oxygen value
Output Format
An integer denoting the the minimum possible value
Constraints
1 <= N <= 105
1 <= O <= 105
0 < T < 107
Sample Input
4
9
12
3
7
5
Sample Output
2Explanation
All possible pairs of [l, r] are: [[0,0],[1, 1],[2,2].[3,3],
[0.1], [1,2]. [2,3], [0,2],[1,3],[0,3]].
For each pair of Il, rl we get the following results for
O[l,r]: [9,12,3,7,8,0,3,0,3,0]. The value closest to 5 is 3 (or 7) and the difference is 2.
You are given a MN binary matrix representing the shape of an item that is supposed to be packed
for shipping. The item to be shipped will always be contiguous. The shipping agency has only rectangular boxes available and they want
minimise the area of the packed item. Find the area of smallest such rectangle formed which would fit the item.
For the given matrix, [0, 1, 0], [0, 1, 11. [0, 0, 011, the area of the smallest rectangle/square needed for packaging would be 2x2 = 4
Function Description
Complete the function getSmallestArea in the editor below. The function should return an integer
representing the smallest area of the rectangle need for packaging.
getSmallestArea has the following parameter(s):
grid/cell|0/0]..cell[m-1][n-1]): a binary array of
integers where 0 represents an empty area and 1
represents a part of the item.
Constraints
• There is only one item of 1's in the matrix i.e. item is
connected throughout horizontally and vertically.
Constraints
0 < arr[i][j] < 1
• There is only one item of 1's in the matrix i.e. item is
connected throughout horizontally and vertically.
• Input Format For Custom Testing
Y Sample Case 0
Samply input For Custom Testing
0 1 0
0 1 1
0 0 0
Sample Output
4
Explanation
The smallest rectangle needed to fit the item would start from index(0, 1) and end on index(1,2) = 2x2 = 4
• Sample Case 1
Sample Input For Custom Testing
0 1 0
0 1 0
0 1 0
Sample Output
3
Explanation
The smallest rectangle needed would have the
same shape as the item itself = 1×3 = 3
Entering edit mode
Problem 2:
This problem can be solved by checking for very subarray .But you might think this will exceed time limit.Here is something interesting about bitwise & that when you take & of a number with another number it will either decrease or remain unchanged .So essentially we only have 32 bits .Suppose all of them are 1 in the starting when you start taking & of this number with elements in the array, some (maybe none) of the bits might become unset (0) ,this is the only possibility. Now if a bit is 1 ,it can convert to 0 or remain 1 and if a bit is 0 it will only remain 0 .This compresses the number of elements we will get after taking & of any subarray to only 32 which gives us the ticket to use map .
we can use map (prev) to store & of subarray ending at i-1 (if we currently are at i) and then we can take & of all these numbers with the current element which will give us & of all the subarrays ending at i .Then at every index we can check for min value of (& of subarray-target) by traversing the map(next) .
Code:
#include <bits/stdc++.h>
using namespace std;
#define f(n, i, x) for (int i = x; i < n; i++)
#define vb push_back
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int target;
cin >> target;
unordered_map<int, int> prev;
int ans = INT_MAX;
for (auto x : a)
{
unordered_map<int, int> next;
for (auto y : prev)
{
next[y.first & x]++;
}
next[x]++;
for(auto y:next){
ans=min(ans,abs(y.first-target));
}
prev = next;
}
cout << ans << endl;
}
Entering edit mode
Problem 1:
It can be solved using recursion .We will check at every index we are at if the string made till now is present in the dictionary or not .Now there arise 2 cases:
Case-1:String exists in the dictionary: In this case we will do 2 recursive steps ,start a new string from next index or continue this string . We are doing the latter step because a case may arise where the current string is present in the dictionary but there is no way we can make remaining string using words in the dictionary .
Case-2:String does not exist in the dictionary : In this case we will just continue the current string.
Now how to do we check whether a string exists in the dictionary in minimum time possible ->using tries which will do the search in O(length of string).
Code:
#include <bits/stdc++.h>
using namespace std;
#define f(n,i,x) for(int i=x;i<n;i++)
#define vb push_back
#define ll long long
class TrieNode {
public:
TrieNode* child[26];
bool isend;
TrieNode() {
for (int i = 0; i < 26; ++i) {
child[i] = NULL;
}
isend = false;
}
};
void insert(string s, TrieNode* root) {
TrieNode* cur = root;
for (int i = 0; i < s.size(); ++i) {
int idx = s[i] - 'a';
if (cur->child[idx] == NULL) {
cur->child[idx] = new TrieNode();
}
cur = cur->child[idx];
}
cur->isend = true;
}
bool search(string s, TrieNode* root) {
TrieNode* cur = root;
for (int i = 0; i < s.size(); ++i) {
int idx = s[i] - 'a';
if (cur->child[idx] == NULL) return false;
cur = cur->child[idx];
}
return cur->isend;
}
bool solve(int i,string s,TrieNode* root,string cur){
if(i==s.size()-1){
if(search(cur+s[i],root)){
return 1;
}
return 0;
}
cur+=s[i];
if(search(cur,root)){
if(solve(i+1,s,root,"")){
return 1;
}
else{
return solve(i+1,s,root,cur);
}
}
return solve(i+1,s,root,cur);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;cin>>n;
TrieNode* root=new TrieNode();
f(n,i,0){
string s;
cin>>s;
insert(s,root);
}
string s;cin>>s;
if(solve(0,s,root,"")){
cout<<"yes"<<endl;
}
}
else{
cout<<"no"<<endl;
}
}
