Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Given a positive integer num
, return the number of positive integers less than or equal to num
whose digit sums are even.
The digit sum of a positive integer is the sum of all its digits.
Example 1:
Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.
Example 2:
Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.
Constraints:
1 <= num <= 1000
class Solution {
public:
int countEven(int num) {
int temp = num, sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum % 2 == 0 ? temp / 2 : (temp - 1) / 2;
}
};
class Solution:
def countEven(self, num: int) -> int:
return num // 2 if sum([int(k) for k in str(num)]) % 2 == 0 else (num - 1) // 2
def countEven(self, num: int) -> int:
n, dSum = num, 0
while n > 0: # Calculate digit sum of numbers
dSum += n%10
n = n//10
if num % 2 == 0 and dSum % 2 == 1:
return num//2 - 1
return num//2
class Solution
{
public int countEven(int num)
{
int count = 0;
for(int i = 1; i <= num; i++)
if(sumDig(i))
count++;
return count;
}
private boolean sumDig(int n)
{
int sum = 0;
while(n > 0)
{
sum += n % 10;
n /= 10;
}
return (sum&1) == 0 ? true : false;
}
}
You are given the head
of a linked list, which contains a series of integers separated by 0
‘s. The beginning and end of the linked list will have Node.val == 0
.
For every two consecutive 0
‘s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0
‘s.
Return the head
of the modified linked list.
Example 1:
Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.
Example 2:
Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.
Constraints:
[3, 2 * 105]
.0 <= Node.val <= 1000
Node.val == 0
.Node.val == 0
. ListNode* mergeNodes(ListNode* head) {
head=head->next;
ListNode* start=head;
while(start){
ListNode* end= start; /* Point to first node of current part for getting sum */
int sum=0;
while(end->val!=0) sum+= end->val , end=end->next;
start->val=sum; /*assign sum to first node between two 0*/
start->next=end->next; /*make this connect to first node of next part*/
start=start->next; /*go..to..next..part*/
}
return head;
}
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(Integer.MIN_VALUE), prev = dummy;
while (head != null && head.next != null) {
prev.next = head; // prev connects next 0 node.
head = head.next; // head forward to a non-zero node.
while (head != null && head.val != 0) { // traverse all non-zero nodes between two zero nodes.
prev.next.val += head.val; // add current value to the previous zero node.
head = head.next; // forward one step.
}
prev = prev.next; // prev point to the summation node (initially 0).
}
prev.next = null; // cut off last 0 node.
return dummy.next;
}
def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = prev = ListNode(-math.inf)
while head and head.next:
prev.next = head
head = head.next
while head and head.val != 0:
prev.next.val += head.val
head = head.next
prev = prev.next
prev.next = None
return dummy.next
class Solution:
def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
ptr1 = head
ptr2 = head.next
s = 0
while ptr2:
if ptr2.val == 0:
ptr1 = ptr1.next
ptr1.val=s
s=0
else:
s+=ptr2.val
ptr2 = ptr2.next
ptr1.next=None
return head.next
You are given a string s
and an integer repeatLimit
. Construct a new string repeatLimitedString
using the characters of s
such that no letter appears more than repeatLimit
times in a row. You do not have to use all characters from s
.
Return the lexicographically largest repeatLimitedString
possible.
A string a
is lexicographically larger than a string b
if in the first position where a
and b
differ, string a
has a letter that appears later in the alphabet than the corresponding letter in b
. If the first min(a.length, b.length)
characters do not differ, then the longer string is the lexicographically larger one.
Example 1:
Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.
Example 2:
Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.
Constraints:
1 <= repeatLimit <= s.length <= 105
s
consists of lowercase English letters.class Solution {
public:
string repeatLimitedString(string s, int k) { // k is the repeatLimit
int n = s.length();
unordered_map<char,int> m;
for(int i=0;i<n;i++) m[s[i]]++;
priority_queue<pair<char,int>> pq;
for(auto i: m){
pq.push({i.first,i.second}); // pushing the characters with their frequencies.
}
string ans = "";
while(!pq.empty()){
char c1 = pq.top().first;
int n1 = pq.top().second;
pq.pop();
int len = min(k,n1); // Adding characters upto minimum of repeatLimit and present character count.
for(int i=0;i<len;i++){ // adding the highest priority element to the ans.
ans += c1;
}
char c2;
int n2=0;
if(n1-len>0){ // If the cnt of present character is more than the limit.
if(!pq.empty()){ //Getting the next priority character.
c2 = pq.top().first;
n2 = pq.top().second;
pq.pop();
}
else{
return ans; // if there is no another letter to add, we just return ans.
}
ans += c2; // Adding next priority character to ans.
// If the elements are left out, pushing them back into priority queue for next use.
pq.push({c1,n1-len});
if(n2-1>0) pq.push({c2,n2-1});
}
}
return ans;
}
};
public String repeatLimitedString(String s, int repeatLimit) {
PriorityQueue<Character> pq = new PriorityQueue<Character>((a,b)->b-a);
for(char ch:s.toCharArray()){
pq.add(ch);
}
StringBuffer res = new StringBuffer();
ArrayList<Character> list = new ArrayList<Character>();
Stack<Character> stk = new Stack<Character>();
int count = 0;
char previouschar = pq.peek();
while(!pq.isEmpty()){
char curr = pq.poll();
if(curr==previouschar){
if(count<repeatLimit){
res.append(curr);
}
else{
stk.add(curr);
}
count++;
}
else{
if(stk.isEmpty()){
count=0;
res.append(curr);
previouschar = curr;
count++;
}
else{
res.append(curr);
count=0;
while(!stk.isEmpty() && count<repeatLimit){
res.append(stk.pop());
count++;
}
}
}
}
return res.toString();
}
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
pq = [(-ord(k), v) for k, v in Counter(s).items()]
heapify(pq)
ans = []
while pq:
k, v = heappop(pq)
if ans and ans[-1] == k:
if not pq: break
kk, vv = heappop(pq)
ans.append(kk)
if vv-1: heappush(pq, (kk, vv-1))
heappush(pq, (k, v))
else:
m = min(v, repeatLimit)
ans.extend([k]*m)
if v-m: heappush(pq, (k, v-m))
return "".join(chr(-x) for x in ans)
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
arr = [0] * 26
a = ord('a')
for char in s:
arr[ord(char)-a] += 1
# Using an array to store the answer as appending to a string is a costly operation
ans = []
curr = 25
prev = 24
# We are starting with curr = 25 as we need to add the largest character first
while curr >= 0:
if arr[curr] == 0:
curr -= 1
continue
# If the character is present in the string then we add it to our answer
for i in range(min(repeatLimit, arr[curr])):
ans.append(chr(curr + a))
arr[curr] -= 1
# If the above for loop was able to add all the characters then we can move on to the next one
if arr[curr] == 0:
curr -= 1
continue
# If the above for loop was not able to add all the characters then we need to add a second largest character before we can continue adding the largest character to our answer again
g = False
for j in range(min(prev, curr-1), -1, -1):
if arr[j]:
g = True
arr[j] -= 1
prev = j
ans.append(chr(j+a))
break
# If g is false then we know that there were no other characters present other than the largest character
if not g: break
return ''.join(ans)
Given a 0-indexed integer array nums
of length n
and an integer k
, return the number of pairs (i, j)
such that:
0 <= i < j <= n - 1
andnums[i] * nums[j]
is divisible by k
.Example 1:
Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation:
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.
Constraints:
1 <= nums.length <= 105
1 <= nums[i], k <= 105
public long countPairs(int[] nums, int k) {
Map<Long, Long> cnt = new HashMap<>();
long res = 0L;
for (int x : nums) {
cnt.merge(BigInteger.valueOf(x).gcd(BigInteger.valueOf(k)).longValue(), 1L, Long::sum);
}
for (long x : cnt.keySet()) {
for (long y : cnt.keySet()) {
if (x <= y && x * y % k == 0L) {
res += x < y ? cnt.get(x) * cnt.get(y) : cnt.get(x) * (cnt.get(x) - 1L) / 2L;
}
}
}
return res;
}
long long coutPairs(vector<int>& nums, int k) {
unordered_map<int, int> mp;
for (int& nu: nums) {
mp[gcd(nu, k)]++;
}
long long res = 0;
for (auto& [a, c1]: mp) {
for (auto & [b, c2]: mp) {
if (a <= b && a*(long) b %k == 0) {
res += a < b?(long)c1*c2:(long)c1*(c1-1)/2;
}
}
}
return res;
}
def coutPairs(self, A, k):
cnt = Counter(math.gcd(a, k) for a in A)
res = 0
for a in cnt:
for b in cnt:
if a <= b and a * b % k == 0:
res += cnt[a] * cnt[b] if a < b else cnt[a] * (cnt[a] - 1) // 2
return res
class Solution:
def coutPairs(self, nums: List[int], k: int) -> int:
factors = []
for x in range(1, int(sqrt(k))+1):
if k % x == 0: factors.append(x)
ans = 0
freq = Counter()
for x in nums:
x = gcd(x, k)
ans += freq[k//x]
for f in factors:
if x % f == 0 and f <= x//f:
freq[f] += 1
if f < x//f: freq[x//f] += 1
return ans
In our experience, we suggest you solve this Weekly Contest 281 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 281 LeetCode Solution
I hope this Weekly Contest 281 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 >>