loading...

Daily Coding Challenge #44

wingkwong profile image Wing-Kam ใƒป2 min read

Daily Coding Challenge (87 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 85 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

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.


/*
Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
*/

class Solution {
public:
    int numTrees(int n) {
        // dp approach to find Catalan Number
        vector<int> catalan(n+1);
        catalan[0]=catalan[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<i;j++){
                catalan[i]+=catalan[j]*catalan[i-j-1];
            }
        }
        return catalan[n];       
    }
};

/*
Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2
Example 2:

Input: [3,1,3,4,2]
Output: 3
Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
*/

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // Floyd's Tortoise and Hare (Cycle Detection)
        int fast,slow;
        fast=slow=nums[0];
        while(1){
            // phase 1
            // construct a sequence like x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ...
            fast=nums[fast];
            slow=nums[nums[slow]];
            if(fast==slow) break;
        }
        slow=nums[0];
        while(fast!=slow){
            // phase 2
            // slow starts from entrance point
            // fast starts from intersection point
            fast=nums[fast];
            slow=nums[slow];
        }
        return slow;
    }
};

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 (87 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 85 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

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide