Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Weekly Contest 278 LeetCode Solution
Problem 1 – Keep Multiplying Found Values by Two Leetcode Solution
You are given an array of integers nums. You are also given an integer original which is the first number that needs to be searched for in nums.
You then do the following steps:
- If
originalis found innums, multiply it by two (i.e., setoriginal = 2 * original). - Otherwise, stop the process.
- Repeat this process with the new number as long as you keep finding the number.
Return the final value of original.
Example 1:
Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation:
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
- 24 is not found in nums. Thus, 24 is returned.
Example 2:
Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
- 4 is not found in nums. Thus, 4 is returned.
Constraints:
1 <= nums.length <= 10001 <= nums[i], original <= 1000
Keep Multiplying Found Values by Two Leetcode Solution in C++
int findFinalValue(vector<int>& nums, int o) {
int h[1001]={};
for(auto i:nums) h[i]++;
while(o<=1000 && h[o])
o*=2;
return o;
}
Keep Multiplying Found Values by Two Leetcode Solution in Java
class Solution
{
public int findFinalValue(int[] nums, int original)
{
HashSet<Integer> set = new HashSet<>();
for(int i : nums)
if(i >= original)
set.add(i);
while(true)
if(set.contains(original))
original *= 2;
else
break;
return original;
}
}
Keep Multiplying Found Values by Two Leetcode Solution in Python
class Solution:
def findFinalValue(self, nums: List[int], og: int) -> int:
return og if og not in nums else self.findFinalValue(nums, 2 * og)
Problem 2 – All Divisions With the Highest Score of a Binary Array Leetcode Solution
You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) numsleft and numsright:
numslefthas all the elements ofnumsbetween index0andi - 1(inclusive), whilenumsrighthas all the elements of nums between indexiandn - 1(inclusive).- If
i == 0,numsleftis empty, whilenumsrighthas all the elements ofnums. - If
i == n,numslefthas all the elements of nums, whilenumsrightis empty.
The division score of an index i is the sum of the number of 0‘s in numsleft and the number of 1‘s in numsright.
Return all distinct indices that have the highest possible division score. You may return the answer in any order.
Example 1:
Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
- 2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
- 3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.
Example 2:
Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.
Example 3:
Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.
Constraints:
n == nums.length1 <= n <= 105nums[i]is either0or1.
All Divisions With the Highest Score of a Binary Array Leetcode Solution in C++
vector<int> maxScoreIndices(vector<int>& nums) {
int rightOne=accumulate(begin(nums),end(nums),0),leftZero=0,maxScore=0;
vector<int>res;
for(int i=0;i<=nums.size();i++){
if(rightOne+leftZero > maxScore){
maxScore=rightOne+leftZero;
res.clear();
res.push_back(i);
}
else if(rightOne+leftZero == maxScore) res.push_back(i);
if(i!=nums.size()){
if(nums[i]==0)leftZero++;
if(nums[i]==1)rightOne--;
}
}
return res;
}
All Divisions With the Highest Score of a Binary Array Leetcode Solution in Java
class Solution {
public List<Integer> maxScoreIndices(int[] nums) {
int N = nums.length;
List<Integer> res = new ArrayList<>();
int[] pref = new int[N + 1];
pref[0] = 0; // at zeroth division we have no elements
for(int i = 0; i < N; ++i) pref[i+1] = nums[i] + pref[i];
int maxScore = -1;
int onesToRight, zeroesToLeft, currScore;
for(int i = 0; i < N + 1; ++i) {
onesToRight = pref[N] - pref[i];
zeroesToLeft = i - pref[i];
currScore = zeroesToLeft + onesToRight;
if(currScore > maxScore) {
res.clear();
maxScore = currScore;
}
if(currScore == maxScore) res.add(i);
}
return res;
}
}
All Divisions With the Highest Score of a Binary Array Leetcode Solution in Python
class Solution:
def maxScoreIndices(self, nums: List[int]) -> List[int]:
left_div_score = 0
right_div_score = sum(nums)
div_sum = [left_div_score+right_div_score]
for i in range(len(nums)):
if nums[i]==0:
left_div_score+=1
if nums[i]==1:
right_div_score-=1
div_sum.append(left_div_score+right_div_score)
max_val = max(div_sum)
return( [i for i, v in enumerate(div_sum) if v==max_val])
Problem 3 – Find Substring With Given Hash Value Leetcode Solution
The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function:
hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26.
You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.
The test cases will be generated such that an answer always exists.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0.
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".
Example 2:
Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32.
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32.
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".
Constraints:
1 <= k <= s.length <= 2 * 1041 <= power, modulo <= 1090 <= hashValue < modulosconsists of lowercase English letters only.- The test cases are generated such that an answer always exists.
Find Substring With Given Hash Value Leetcode Solution in Java
public String subStrHash(String s, int p, int m, int k, int hashValue) {
long cur = 0, pk = 1;
int res = 0, n = s.length();
for (int i = n - 1; i >= 0; --i) {
cur = (cur * p + s.charAt(i) - 'a' + 1) % m;
if (i + k >= n)
pk = pk * p % m;
else
cur = (cur - (s.charAt(i + k) - 'a' + 1) * pk % m + m) % m;
if (cur == hashValue)
res = i;
}
return s.substring(res, res + k);
}
Find Substring With Given Hash Value Leetcode Solution in C++
string subStrHash(string s, int p, int m, int k, int hashValue) {
long long cur = 0, res = 0, pk = 1, n = s.size();
for (int i = n - 1; i >= 0; --i) {
cur = (cur * p + s[i] - 'a' + 1) % m;
if (i + k >= n)
pk = pk * p % m;
else
cur = (cur - (s[i + k] - 'a' + 1) * pk % m + m) % m;
if (cur == hashValue)
res = i;
}
return s.substr(res, k);
}
Find Substring With Given Hash Value Leetcode Solution in Python
def subStrHash(self, s, p, m, k, hashValue):
def val(c):
return ord(c) - ord('a') + 1
res = n = len(s)
pk = pow(p,k,m)
cur = 0
for i in xrange(n - 1, -1, -1):
cur = (cur * p + val(s[i])) % m
if i + k < n:
cur = (cur - val(s[i + k]) * pk) % m
if cur == hashValue:
res = i
return s[res: res + k]
Problem 4 – Groups of Strings Leetcode Solution
You are given a 0-indexed array of strings words. Each string consists of lowercase English letters only. No letter occurs more than once in any string of words.
Two strings s1 and s2 are said to be connected if the set of letters of s2 can be obtained from the set of letters of s1 by any one of the following operations:
- Adding exactly one letter to the set of the letters of
s1. - Deleting exactly one letter from the set of the letters of
s1. - Replacing exactly one letter from the set of the letters of
s1with any letter, including itself.
The array words can be divided into one or more non-intersecting groups. A string belongs to a group if any one of the following is true:
- It is connected to at least one other string of the group.
- It is the only string present in the group.
Note that the strings in words should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique.
Return an array ans of size 2 where:
ans[0]is the maximum number of groupswordscan be divided into, andans[1]is the size of the largest group.
Example 1:
Input: words = ["a","b","ab","cde"]
Output: [2,3]
Explanation:
- words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2].
- words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2].
- words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1].
- words[3] is not connected to any string in words.
Thus, words can be divided into 2 groups ["a","b","ab"] and ["cde"]. The size of the largest group is 3.
Example 2:
Input: words = ["a","ab","abc"]
Output: [1,3]
Explanation:
- words[0] is connected to words[1].
- words[1] is connected to words[0] and words[2].
- words[2] is connected to words[1].
Since all strings are connected to each other, they should be grouped together.
Thus, the size of the largest group is 3.
Constraints:
1 <= words.length <= 2 * 1041 <= words[i].length <= 26words[i]consists of lowercase English letters only.- No letter occurs more than once in
words[i].
Groups of Strings Leetcode Solution in C++
unordered_map<int, int> m;
int dfs(int mask) {
int res = 0;
auto it = m.find(mask);
if (it != end(m)) {
res += it->second;
m.erase(it);
for (int i = 0; i < 26; ++i) {
res += dfs(mask ^ (1 << i));
for (int j = i + 1; j < 26; ++j)
if (((mask >> i) & 1) != ((mask >> j) & 1))
res += dfs(mask ^ (1 << i) ^ (1 << j));
}
}
return res;
}
vector<int> groupStrings(vector<string>& words) {
int groups = 0, max_size = 0;
for (auto &w : words)
++m[accumulate(begin(w), end(w), 0, [](int m, char ch){ return m | (1 << (ch - 'a')); })];
while (!m.empty()) {
auto size = dfs(begin(m)->first);
max_size = max(max_size, size);
groups += size > 0;
}
return { groups, max_size };
}
Groups of Strings Leetcode Solution in Python
class Solution:
def groupStrings(self, w):
M = {sum(1<<(ord(i) - ord("a")) for i in word): j for j, word in enumerate(w)}
G = defaultdict(list)
masks = defaultdict(list)
for idx, word in enumerate(w):
vals = [ord(i) - ord("a") for i in word]
mask = sum(1<<i for i in vals)
for i in vals:
masks[mask - (1<<i) + (1<<26)].append(idx)
if mask - (1<<i) not in M: continue
idx2 = M[mask - (1<<i)]
G[idx] += [idx2]
G[idx2] += [idx]
for x in masks.values():
for a, b in zip(x, x[1:]):
G[a] += [b]
G[b] += [a]
V, comps, r = set(), 0, 0
for u in range(len(w)):
if u in V: continue
compsize, q = 1, [u]
V.add(u)
while q:
u = q.pop()
for v in G[u]:
if v in V: continue
compsize += 1
V.add(v)
q += [v]
r = max(r, compsize)
comps += 1
return [comps, r]
Groups of Strings Leetcode Solution in Java
class Solution {
public int[] groupStrings(String[] words) {
int n = words.length;
// System.out.println(n);
UnionFind uf = new UnionFind(n);
// map mask -> original index
Map<Integer, Integer> map = new HashMap<>();
int[] mask = new int[n];
for (int i = 0; i < n; i++) {
int x = 0;
char[] temp = words[i].toCharArray();
for (int j = 0; j < temp.length; j++) {
char c = temp[j];
// set the (c - 'a')th digit to 1
x = x | (1 << (c - 'a'));
}
map.put(x, i);
mask[i] = x;
}
// start checking words one by one, if it has connected words, join them in Union Find
for (int i = 0; i < n; i++) {
String current = words[i];
int len = current.length();
int x = mask[i];
for (int j = 0; j < len; j++) {
char c = current.charAt(j);
// delete char at j -> set the (c - 'a')th digit to 0
x = x & (~(1 << (c - 'a')));
if (map.containsKey(x)) {
int next = map.get(x);
uf.join(i, next);
}
// replace char at j with 'a' to 'z':
// replace = delete(already done) + add
for (char t = 'a'; t <= 'z'; t++) {
// take the bit of the (t - 'a')th digit
int dig = (x >> (t - 'a')) & 1;
if (dig == 1) {
// since no letter occurs more than once in words[i],
// if this digit is already 1, we can continue;
continue;
}
// set the (t - 'a')th digit to 1, complete the replacing
x = x | (1 << (t - 'a'));
if (map.containsKey(x)) {
int next = map.get(x);
uf.join(i, next);
}
// backtracking , set it back to 0
x = x & (~(1 << (t - 'a')));
}
// backtracking, add back the char we delete
x = x | (1 << (c - 'a'));
}
}
// get output from the union Find
Set<Integer> set = new HashSet<>();
int max = 1;
for (int i = 0; i < n; i++) {
int fx = uf.find(i);
set.add(fx);
max = Math.max(max, uf.size[i]);
}
return new int[] {set.size(), max};
}
}
class UnionFind {
int[] father;
int[] size;
public UnionFind(int n) {
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
size = new int[n];
Arrays.fill(size, 1);
}
public void join(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
father[fx] = fy;
size[fy] += size[fx];
}
}
public int find(int x) {
int root = x;
while (father[root] != root) {
root = father[root];
}
while (x != root) {
int fx = father[x];
father[x] = root;
x = fx;
}
return root;
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
Weekly Contest 278 LeetCode Solution Review:
In our experience, we suggest you solve this Weekly Contest 278 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 278 LeetCode Solution
Conclusion:
I hope this Weekly Contest 278 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
