304 North Cardinal St.
Dorchester Center, MA 02124

# 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 == 1`end the process. Otherwise, create a new 0-indexed integer array `newNums` of length `n - 1`.
2. For each index `i`, where `0 <= i < n - 1`assign 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 = 
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
``````

## 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 `1st``3rd`, 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 =  * 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