loading...

Daily Coding Challenge #49

wingkwong profile image Wing-Kam ・3 min read

Daily Coding Challenge (88 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 86 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80 81) Daily Coding Challenge #81 82) Daily Coding Challenge #82 83) Daily Coding Challenge #83 84) Daily Coding Challenge #84 85) Daily Coding Challenge #85 86) Daily Coding Challenge #86 87) Daily Coding Challenge #87 88) Daily Coding Challenge #88

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.


/*
LeetCode - Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. 

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]


Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.
*/

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        string word;
        TrieNode():word(""){
            for(int i=0;i<26;i++) {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* buildTrie(vector<string>& words){
        TrieNode* root = new TrieNode();
        for(string word:words){
            TrieNode *cur = root;
            for(char c:word){
                if(cur->children[c-'a']==nullptr){
                    cur->children[c-'a']=new TrieNode();
                }
                cur = cur->children[c-'a'];
            }
            cur->word = word;
        }
        return root;
    }

    void dfs(int i, int j, vector<vector<char>>& board, TrieNode* root, vector<string>& ans){
        char c=board[i][j];
        // if visited or no such character, return 
        if(c=='*'||!root->children[c-'a']) return;
        root = root->children[c-'a'];
        if(root->word.size()){
            // add it to ans    
            ans.push_back(root->word);
            // de-duplicate from trie node
            root->word="";
        }
        // set it to other character. consider it has been visited
        board[i][j]='*';
        // dfs - 4 directions
        if(i>0) dfs(i-1,j,board,root,ans);
        if(j>0) dfs(i,j-1,board,root,ans);
        if(i<board.size()-1) dfs(i+1,j,board,root,ans);
        if(j<board[0].size()-1) dfs(i,j+1,board,root,ans);
        // backtracking
        board[i][j]=c;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // approach: trie + dfs + backtracking
        // build trie node 
        TrieNode* root = buildTrie(words);
        vector<string> ans;
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                // dfs
                dfs(i,j,board,root,ans);
            }
        }
        return ans;
    }
};

/*
LeetCode - Check If Array Pairs Are Divisible by k

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
Example 4:

Input: arr = [-10,10], k = 2
Output: true
Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true


Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
*/

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int,int> m;
        for(int x:arr) {
            // m[(x%k)]++;  // this line only works for non-negative values
            m[(x%k+k)%k]++; // for negative values, you need to tune it back to a possible value using (x%k+k)%k
            // or m[x%k<0?(x%k)+k:(x%k)]++;
        }
        // return false if we can't make m[0] a pair
        if(m[0]%2==1) return false;
        for(int i=1;i<k;i++){
            // same for others. find the corresponding pair.
            if(m[i]!=m[k-i]){
                // if not found, return false
                return false;
            }
        }
        return true;
    }
};   


class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        // weak test case. still pass with below solution.
        // this case should return false instead of true 
        // [1,1,1,1,1,1]
        // 6
        long long ans=0;
        for(int x:arr) ans+=x; 
        return (ans%k==0); 
    }
};    

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Daily Coding Challenge (88 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 86 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80 81) Daily Coding Challenge #81 82) Daily Coding Challenge #82 83) Daily Coding Challenge #83 84) Daily Coding Challenge #84 85) Daily Coding Challenge #85 86) Daily Coding Challenge #86 87) Daily Coding Challenge #87 88) Daily Coding Challenge #88

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide