Biweekly Contest 75 LeetCode Solution

Problem 1 – Minimum Bit Flips to Convert Number Leetcode Solution

bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

  • For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:

  • 0 <= start, goal <= 109

Minimum Bit Flips to Convert Number Leetcode Solution in C++

class Solution {
public:
    int minBitFlips(int start, int goal) {
        return __builtin_popcount(start^goal);
    }
};

Minimum Bit Flips to Convert Number Leetcode Solution in Java

public int minBitFlips(int start, int goal) {
        return Integer.bitCount(start^goal);
}

Minimum Bit Flips to Convert Number Leetcode Solution in Python

def minBitFlips(self, start: int, goal: int) -> int:
        return (start ^ goal).bit_count()

Minimum Bit Flips to Convert Number Leetcode Solution in JavaScript

var minBitFlips = function(start, goal) {
    return (start^goal).toString(2).split("0").join("").length;
};

Problem 2 – Find Triangular Sum of an Array Leetcode Solution

You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

  1. Let nums comprise of n elements. If n == 1end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
  2. For each index i, where 0 <= i < n - 1assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
  3. Replace the array nums with newNums.
  4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Example 1:

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 9

Find Triangular Sum of an Array Leetcode Solution in Python3

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        return sum(n * comb(len(nums) - 1, i) for i, n in enumerate(nums)) % 10

Find Triangular Sum of an Array Leetcode Solution in C++

int triangularSum(vector<int>& nums) {
    int result = 0;
    int m = nums.size() - 1;
    int mck = 1, exp2 = 0, exp5 = 0;
    int inv[] = {0, 1, 0, 7, 0, 0, 0, 3, 0, 9};
    int pow2mod10[] = {6, 2, 4, 8};        
    for (int k = 0; true; k++) {
        if (!exp2 || !exp5) {
            int mCk_ = exp2 ? mck * pow2mod10[exp2 % 4] :
                       exp5 ? mck * 5 : mck;
            result = (result + mCk_ * nums[k]) % 10;
        }
        if (k == m)
            return result;

        // mCk *= m - k
        int mul = m - k;
        while (mul % 2 == 0) {
            mul /= 2;
            exp2++;
        }
        while (mul % 5 == 0) {
            mul /= 5;
            exp5++;
        }
        mck = mck * mul % 10;

        // mCk /= k + 1
        int div = k + 1;
        while (div % 2 == 0) {
            div /= 2;
            exp2--;
        }
        while (div % 5 == 0) {
            div /= 5;
            exp5--;
        }
        mck = mck * inv[div % 10] % 10;
    }
}

Find Triangular Sum of an Array Leetcode Solution in Java

public int triangularSum(int[] nums) {
    int result = 0;
    int m = nums.length - 1;
    int mck = 1, exp2 = 0, exp5 = 0;
    int[] inv = {0, 1, 0, 7, 0, 0, 0, 3, 0, 9};
    int[] pow2mod10 = {6, 2, 4, 8};
    for (int k = 0; true; k++) {
        if (exp2 == 0 || exp5 == 0) {
            int mCk_ = exp2 > 0 ? mck * pow2mod10[exp2 % 4] :
                       exp5 > 0 ? mck * 5 : mck;
            result = (result + mCk_ * nums[k]) % 10;
        }
        if (k == m)
            return result;

        // mCk *= m - k
        int mul = m - k;
        while (mul % 2 == 0) {
            mul /= 2;
            exp2++;
        }
        while (mul % 5 == 0) {
            mul /= 5;
            exp5++;
        }
        mck = mck * mul % 10;

        // mCk /= k + 1
        int div = k + 1;
        while (div % 2 == 0) {
            div /= 2;
            exp2--;
        }
        while (div % 5 == 0) {
            div /= 5;
            exp5--;
        }
        mck = mck * inv[div % 10] % 10;
    }
}

Find Triangular Sum of an Array Leetcode Solution in Python

class Solution:
    def func(self,v):
        for i in range(0,len(v)-1):
            v[i]=(v[i]+v[i+1])%10
        v.pop()
    
    def triangularSum(self, nums: List[int]) -> int:
        while(len(nums)>1):
            self.func(nums)
        return nums[0]

Problem 3 – Number of Ways to Select Buildings Leetcode Solution

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

  • s[i] = '0' denotes that the ith building is an office and
  • s[i] = '1' denotes that the ith building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

  • For example, given s = "001101", we cannot select the 1st3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints:

  • 3 <= s.length <= 105
  • s[i] is either '0' or '1'.

Number of Ways to Select Buildings Leetcode Solution in C++

class Solution {
public:
    long long numberOfWays(string s) {
        long long a=0,b=0,ans=0;        // a and b are the number of occurances of '1' and '0' after the current building respectively.
        for(int i=0;i<s.length();i++){
            if(s[i]=='1')
                a++;
            else
                b++;
        }
        long long c=0,d=0;              // c and d are the number of occurances of '1' and '0' before the current building respectively.
        for(int i=0;i<s.length();i++){
            if(s[i]=='1'){               // Counting the sequences of "010"
                ans+=(d*b);
                a--;
                c++;
            }
            else{                        // Counting the sequences of "101"
                ans+=(a*c);
                b--;
                d++;
            }
        }
        return ans;
    }
};

Number of Ways to Select Buildings Leetcode Solution in Java

class Solution {
    public long numberOfWays(String s) {
        long ans = 0;
        int len = s.length();
        
        long totZeros = 0;
        
        for(int i=0;i<len;i++){
            totZeros += s.charAt(i)=='0'?1:0;
        }
        
        long totOnes = len - totZeros;
        
        long currZeros = s.charAt(0)=='0'?1:0;
        long currOnes = s.charAt(0)=='1'?1:0;
        
        for(int i=1;i<len;i++){
            if(s.charAt(i) == '0'){
                ans = ans + (currOnes * (totOnes-currOnes));
                currZeros++;
            }else{
                ans = ans + (currZeros * (totZeros-currZeros));
                currOnes++;
            }
        }
        return ans;
    }
}

Number of Ways to Select Buildings Leetcode Solution in Python

class Solution:
    def numberOfWays(self, s: str) -> int:
        dp = {"0": 0, "1": 0, "01": 0, "10": 0, "010": 0, "101": 0}
        for i in range(len(s)):
            if s[i] == "0":
                dp["0"] += 1
                dp["10"] += dp["1"]
                dp["010"] += dp["01"]
            if s[i] == "1":
                dp["1"] += 1
                dp["01"] += dp["0"]
                dp["101"] += dp["10"]
                
        return dp["010"] + dp["101"]

Problem 4 – Sum of Scores of Built Strings Leetcode Solution

You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled si.

  • For example, for s = "abaca"s1 == "a"s2 == "ca"s3 == "aca", etc.

The score of si is the length of the longest common prefix between si and sn (Note that s == sn).

Given the final string s, return the sum of the score of every si.

Example 1:

Input: s = "babab"
Output: 9
Explanation:
For s1 == "b", the longest common prefix is "b" which has a score of 1.
For s2 == "ab", there is no common prefix so the score is 0.
For s3 == "bab", the longest common prefix is "bab" which has a score of 3.
For s4 == "abab", there is no common prefix so the score is 0.
For s5 == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.

Example 2:

Input: s = "azbazbzaz"
Output: 14
Explanation: 
For s2 == "az", the longest common prefix is "az" which has a score of 2.
For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other si, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Sum of Scores of Built Strings Leetcode Solution in Python

class Solution:
    def sumScores(self, s):
        def z_function(s):
            n = len(s)
            z = [0] * n
            l, r = 0, 0
            for i in range(1, n):
                if i <= r:
                    z[i] = min(r - i + 1, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] - 1 > r:
                    l, r = i, i + z[i] - 1
            return z
        
        return sum(z_function(s)) + len(s)

Sum of Scores of Built Strings Leetcode Solution in C++

Approach 1: LPS (KMP)

vector<int> lps(string &s) {
    vector<int> lps(s.size());
    for (int i = 1, j = 0; i < s.size(); ++i) {
        while (j && s[i] != s[j])
            j = max(0, lps[j - 1]);
        j += s[i] == s[j];
        lps[i] = j;
    }
    return lps;
}    
long long sumScores(string s) {
    vector<int> cnt;
    for (int j :  lps(s))
        cnt.push_back(j == 0 ? 0 : cnt[j - 1] + 1);   
    return accumulate(begin(cnt), end(cnt), 0LL) + s.size();
}

Approach 2: Z-function

vector<int> z(string &s) {
    vector<int> z(s.size());
    int l = 0, r = 1;
    for (int i = 1; i < s.size(); ++i) {
        z[i] = i > r ? 0 : min(r - i, z[i - l]);
        while (i + z[i] < s.size() && s[z[i]] == s[z[i] + i])
            ++z[i];
       if (z[i] + i > r) {
           l = i;
           r = z[i] + i;
        }
    }
    return z;
}
long long sumScores(string s) {
    vector<int> cnt = z(s);
    return accumulate(begin(cnt), end(cnt), 0LL) + s.size();
}

Sum of Scores of Built Strings Leetcode Solution in Java

public int[] calculateZ(char[] input) {
	int[] Z = new int[input.length];
	int left = 0, right = 0;
	for (int i = 1; i < input.length; i++) {
		if (i > right) {
			left = right = i;
			while (right < input.length && input[right] == input[right - left]) {
				right++;
			}
			Z[i] = right - left;
			right--;
		} else {
			int k = i - left;
			if (Z[k] < right - i + 1) {
				Z[i] = Z[k];
			} else {
				left = i;
				while (right < input.length && input[right] == input[right - left]) {
					right++;
				}
				Z[i] = right - left;
				right--;
			}
		}
	}
	return Z;
}

public long sumScores(String s) {
	int[] z = calculateZ(s.toCharArray());

	long sum = 0;
	for(int el: z)
		sum += el;
	sum += s.length();
	return sum;
}

Sum of Scores of Built Strings Leetcode Solution in JavaScript

const sumScores = (s) => {
  return s.length + zFunction(s).reduce((acc, x) => acc + x, 0);
};

const zFunction = (s) => {
  const n = s.length;
  const Z = Array(n).fill(0);
  let left = 0, right = 0;
  for (let i = 1; i < n; ++i) {
    if (i <= right)
      Z[i] = Math.min(right - i + 1, Z[i - left]);
    while (i + Z[i] < n && s[Z[i]] === s[i + Z[i]])
      Z[i] += 1;
    if (i + Z[i] - 1 > right) {
      left = i;
      right = i + Z[i] - 1;
    }
  }
  return Z;
};
Biweekly Contest 75 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 75 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 Biweekly Contest 75 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Biweekly Contest 75 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.