Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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
.
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
class Solution {
public:
int minBitFlips(int start, int goal) {
return __builtin_popcount(start^goal);
}
};
public int minBitFlips(int start, int goal) {
return Integer.bitCount(start^goal);
}
def minBitFlips(self, start: int, goal: int) -> int:
return (start ^ goal).bit_count()
var minBitFlips = function(start, goal) {
return (start^goal).toString(2).split("0").join("").length;
};
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:
nums
comprise of n
elements. If n == 1
, end the process. Otherwise, create a new 0-indexed integer array newNums
of length n - 1
.i
, where 0 <= i < n - 1
, assign the value of newNums[i]
as (nums[i] + nums[i+1]) % 10
, where %
denotes modulo operator.nums
with newNums
.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
class Solution:
def triangularSum(self, nums: List[int]) -> int:
return sum(n * comb(len(nums) - 1, i) for i, n in enumerate(nums)) % 10
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;
}
}
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;
}
}
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]
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 ands[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.
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'
.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;
}
};
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;
}
}
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"]
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
.
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.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)
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();
}
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;
}
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;
};
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
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 >>