Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Biweekly Contest 75 LeetCode Solution
Problem 1 – Minimum Bit Flips to Convert Number Leetcode Solution
A 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 is111and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get110, flip the second bit from the right to get101, flip the fifth bit from the right (a leading zero) to get10111, 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:
- Let
numscomprise ofnelements. Ifn == 1, end the process. Otherwise, create a new 0-indexed integer arraynewNumsof lengthn - 1. - For each index
i, where0 <= i < n - 1, assign the value ofnewNums[i]as(nums[i] + nums[i+1]) % 10, where%denotes modulo operator. - Replace the array
numswithnewNums. - 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 <= 10000 <= 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 theithbuilding is an office ands[i] = '1'denotes that theithbuilding 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 the1st,3rd, and5thbuildings 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 <= 105s[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 <= 105sconsists 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
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 >>
