# Leetcode 30 days May Challenge
## Week-1
### Day1: First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API `bool isBadVersion(version)` which will return whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
**Example:**
```markdown
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3)-> false
call isBadVersion(5)-> true
call isBadVersion(4)-> true
Then 4 is the first bad version.
```
***
Approach-1:
> Brute Force (`Linear Scan`) - TLE with large input <br>
> Time Complexity - O(n) <br>
> Space Complexity - O(1)
```cpp=
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
for (int i = 1; i <= n; i++) {
if (isBadVersion(i) == true) {
return i;
break;
}
}
return -1;
}
};
```
*Submission Analysis* -
```markdown
12 / 22 test cases passed.
Status: Time Limit Exceeded(TLE)
Last executed input: 1420736637 1150769282 [n, first_bad_number]
```
***
Approach-2:
> `Binary Search` for bad Version
> Time Complexity - O(logn)
> Space Complexity - O(1)
```cpp=
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l <= r) {
int mid = l + (r-l)/2;
if (isBadVersion(mid) == true && isBadVersion(mid-1) == false)
return mid;
else if (isBadVersion(mid) == true && isBadVersion(mid-1) == true)
r = mid;
else
l = mid+1;
}
return -1;
}
};
```
*Submission Analysis* -
```markdown
22 / 22 test cases passed.
Status: Accepted
Runtime: 0 ms
Memory Usage: 5.8 MB
```
### Day2: Jewels and Stones
You're given strings `J` representing the types of stones that are jewels, and `S` representing the stones you have. Each character in `S` is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in `J` are guaranteed distinct, and all characters in `J` and `S` are letters. Letters are case sensitive, so `"a"` is considered a different type of stone from `"A"`.
**Example 1:**
```markdown
Input: J = "aA", S = "aAAbbbb"
Output: 3
```
**Example 2:**
```markdown
Input: J = "z", S = "ZZ"
Output: 0
```
**Note:**
- `S` and `J` will consist of letters and have length at most 50.
- The characters in `J` are distinct.
***
Approach-1:
> Approach - Linear scan ( For each stone, check if it is a jewel) <br>
> Time Complexity - O(J*S) <br>
> Space Complexity - O(1)
```cpp
class Solution {
public:
/* For each stone, check if it is a jewel. */
int numJewelsInStones(string J, string S) {
int count = 0;
for (char& ch_s : S) {
for (char& ch_j : J) {
if (ch_s == ch_j) {
count++;
}
}
}
return count;
}
```
*Submission Analysis* -
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms
Memory Usage: 6 MB
```
Approach-2:
> `Set` of Stones and check if jewels is there (Since jewels are `unique`, given) <br>
> Time Complexity - O(J + S) <br>
> Space Complexity - O(S)
```cpp
int numJewelsInStones(string J, string S) {
set<char> jewels; // <- Set O(logJ) <- Balanced BST based
for (char& j : J) {
jewels.insert(j);
}
int count = 0;
for (char& s : S) {
if (jewels.find(s) != jewels.end()) {
count++;
}
}
return count;
}
```
*Submission Analysis* -
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms (But, actually more in approximation)
Memory Usage: 6.3 MB
```
> NOTE: Another variation can be:-
```cpp
unordered_multiset<char> jewels;// <- `Unordered_Mutiset` O(1) <- Hash based [Here took more time and space, why?]
```
*Submission Analysis* -
```markdown
254 / 254 test cases passed.
Status: Accepted
Runtime: 0 ms (But, actually more in approximation) then `Set`
Memory Usage: 6.5 MB
```
***
### Day3: P3...
Sign in with Wallet
Connect another wallet