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 numsmultiply 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.
- 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 <= 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[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 nnums 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 == 0numsleft is empty, while numsright has all the elements of nums.
  • If i == nnumsleft 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 [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.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] = 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 powermodulok, 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[0] is the maximum number of groups words can be divided into, and
  • ans[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 * 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 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

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

Leave a Reply

Your email address will not be published.