loading...

Daily Coding Challenge #115

wingkwong profile image Wing-Kam ・3 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Matrix Diagonal Sum
https://leetcode.com/problems/matrix-diagonal-sum/

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.



Example 1:


Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.
Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8
Example 3:

Input: mat = [[5]]
Output: 5


Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100
*/

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int ans=0, n=mat.size();
        for(int i=0;i<n;i++){
            // left diagonal (primary)
            ans+=mat[i][i]; 
            // right diagonal (secondary)
            ans+=mat[i][n-i-1];
        }
        // if n is odd, mat[n/2][n/2] was calculated twice
        // so substract mat[n/2][n/2] 
        return n&1?ans-mat[n/2][n/2]:ans;
    }
};

/*
Number of Ways to Split a String
https://leetcode.com/problems/number-of-ways-to-split-a-string/

Given a binary string s (a string consisting only of '0's and '1's), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters '1' is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.



Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"
Example 2:

Input: s = "1001"
Output: 0
Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"
Example 4:

Input: s = "100100010100110"
Output: 12


Constraints:

s[i] == '0' or s[i] == '1'
3 <= s.length <= 10^5
*/


// #math #combination 
class Solution {
public:
    int numWays(string s) {
        int n = s.size(), mod=1e9+7;
        vector<int> v;
        // store the index of 1
        for(int i=0;i<n;i++) if(s[i]=='1') v.push_back(i);
        int x = v.size();
        // case 1: number of 1s is not divisibe by 3
        if(x%3) return 0; 
        // case 2: number of 1s is 1
        // choice to put the first separator is n-1
        // choice to put the first separator is n-2
        // divide by 2 to remove the repeated case
        if(x==0) return ((long long)(n-2)*(n-1)/2)%mod; 
        // case 3: numer of 1s is divisibe by 3
        return ((long long)(v[(x/3)]-v[(x/3)-1])*(v[2*(x/3)]-v[2*(x/3)-1]))%mod;
    }
};

/*
Caesar Cipher
https://binarysearch.io/problems/Caesar-Cipher

You are given a lowercase alphabet string s, and an offset integer k. Replace every letter in s with a letter k positions further along the alphabet.

Note: If the letter overflows past a or z, it gets wrapped around the other side.

Example 1
Input

s = "abc"
k = 2
Output

"cde"
Explanation

"abc" gets moved 2 positions to the right.

Example 2
Input

s = "aaa"
k = -1
Output

"zzz"
Example 3
Input

s = "zzz"
k = 1
Output

"aaa"
Explanation

The "z" gets wrapped to "a"
*/


#include "solution.hpp"
using namespace std;


class Solution {
    public:
    string solve(string s, int k) {
        /*
        If k is negative, we need to find the positive modulo, which can be found by using (k%mod+mod)%mod.

        To the new character, simply add k with mod 26.

        (c-'a') converts char to int
        (c-'a')+k add the offset
        (((c-'a')+k)%26) after adding the offset, it may exceed 122 (which is z). Hence we need to take mod 26.
        (((c-'a')+k)%26)+'a' converts it back to char
        */
        string ans;
        if(k<0) k=(k%26+26)%26;
        for(char c:s) ans+=(((c-'a')+k)%26)+'a';
        return ans;
    }
};

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / competitive-programming

🌟 My CP Journey - This repository contains CP solutions (mostly written in C++) from different OJs and contest sites 🌟

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide