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:

1. If `original` is found in `nums`multiply it by two (i.e., set `original = 2 * original`).
2. Otherwise, stop the process.
3. 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.
``````

Example 2:

``````Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
``````

Constraints:

• `1 <= nums.length <= 1000`
• `1 <= nums[i], original <= 1000`

### Keep Multiplying Found Values by Two Leetcode Solution in C++

``````int findFinalValue(vector<int>& nums, int o) {
int h={};
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)
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`:

• `numsleft` has all the elements of `nums` between index `0` and `i - 1` (inclusive), while `numsright` has all the elements of nums between index `i` and `n - 1` (inclusive).
• If `i == 0``numsleft` is empty, while `numsright` has all the elements of `nums`.
• If `i == n``numsleft` has all the elements of nums, while `numsright` is 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 . 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 . 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: 
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is . numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is . 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: 
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is . numsright is . 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.length`
• `1 <= n <= 105`
• `nums[i]` is either `0` or `1`.

### 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; // 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;
}
}
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) * p0 + val(s) * 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.

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 * 104`
• `1 <= power, modulo <= 109`
• `0 <= hashValue < modulo`
• `s` consists 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 `s1` with 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` is the maximum number of groups `words` can be divided into, and
• `ans` is the size of the largest group.

Example 1:

``````Input: words = ["a","b","ab","cde"]
Output: [2,3]
Explanation:
- words can be used to obtain words (by replacing 'a' with 'b'), and words (by adding 'b'). So words is connected to words and words.
- words can be used to obtain words (by replacing 'b' with 'a'), and words (by adding 'a'). So words is connected to words and words.
- words can be used to obtain words (by deleting 'b'), and words (by deleting 'a'). So words is connected to words and words.
- words 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 is connected to words.
- words is connected to words and words.
- words is connected to words.
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 * 104`
• `1 <= words[i].length <= 26`
• `words[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 res = 0;
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)
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:
if mask - (1<<i) not in M: continue
G[idx] += [idx2]
G[idx2] += [idx]

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]
while q:
u = q.pop()
for v in G[u]:
if v in V: continue
compsize += 1
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<>();

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);
}

// 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();

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':
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);
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

Find on LeetCode

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

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions