Entering edit mode

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:
true
```

• 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

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.

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

An integer denoting the the minimum possible value

Constraints

1 <= N <= 10^{5}

1 <= O <= 10^{5}

0 < T < 10^{7 }

```
Sample Input
4
9
12
3
7
5
Sample Output
2
```

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

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.

• There is only one item of 1's in the matrix i.e. item is

connected throughout horizontally and vertically.

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
```

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

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;

}

}

Loading Similar Posts