loading...

Daily Coding Challenge #153

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.


/*
Longest ZigZag Path in a Binary Tree
https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

Given a binary tree root, a ZigZag path for a binary tree is defined as follow:

Choose any node in the binary tree and a direction (right or left).
If the current direction is right then move to the right child of the current node otherwise move to the left child.
Change the direction from right to left or right to left.
Repeat the second and third step until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.



Example 1:



Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:



Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:

Input: root = [1]
Output: 0


Constraints:

Each tree has at most 50000 nodes..
Each node's value is between [1, 100].

*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int zigzag(TreeNode* root, int left, int cnt) {
        if(!root) return cnt;
        if(left) return max(zigzag(root->right, 0, cnt+1), zigzag(root->left, 1, 0));
        else return max(zigzag(root->left, 1, cnt+1), zigzag(root->right, 0, 0));
    }
    int longestZigZag(TreeNode* root) {
        if(!root) return 0;
        return max(zigzag(root->left,1,0), zigzag(root->right,0,0));
    }
};
Enter fullscreen mode Exit fullscreen mode

/*
ZigZag Path
https://binarysearch.com/problems/ZigZag-Path

Given a binary tree root, return the longest path that alternates between going down to one child to the other child. For example, it may alternate between right child, left child, right child etc. Or left child, right child, left child...

For example, given

   0
  / \
 1   9
    / \
   4   2
    \
     3
    /
   7
Return 5 since the longest zigzag path is 0 -> 9 -> 4 -> 3 -> 7.

Example 1
Input

root = [0, [0, null, null], null]
Output

2
*/

#include "solution.hpp"
using namespace std;

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
class Solution {
    public:
    int zigzag(Tree* root, int left, int cnt) {
        if(!root) return cnt;
        if(left) return max(zigzag(root->right, 0, cnt+1), zigzag(root->left, 1, 1));
        else return max(zigzag(root->left, 1, cnt+1), zigzag(root->right, 0, 1));
    }
    int solve(Tree* root) {
        if(!root) return 0;
        return max(zigzag(root->left,1,1), zigzag(root->right,0,1));
    }
};
Enter fullscreen mode Exit fullscreen mode

/*
Concatenated Sums
https://binarysearch.com/problems/Concatenated-Sums

You are given a list of non-negative integers nums. Return the sum of every concatenation of every pair of numbers in nums. Note that pairs (i, j) and (j, i) are considered different.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input

nums = [10, 2]
Output

1344
Explanation

We have the following concatenations:

nums[0] + nums[0] = 1010
nums[0] + nums[1] = 102
nums[1] + nums[0] = 210
nums[1] + nums[1] = 22
And its sum is 1344
*/

#include "solution.hpp"
using namespace std;

class Solution {
    public:
    int countBits(int n) {
        if(n == 0) return 1;
        int cnt = 0;
        while(n) {
            cnt++;
            n /= 10;
        }
        return cnt;
     }

    int solve(vector<int>& nums) {
        // nums = [a, b, c]
        // for x in nums
        // ans += x * 10 ^ countBits(x) + a
        // ans += x * 10 ^ countBits(x) + b
        // ans += x * 10 ^ countBits(x) + c
        // let  sum = a + b + c
        //      p   = 10 ^ countBits(a) + 10 ^ countBits(b) + 10 ^ countBits(c)
        // ans = ( a * p + sum ) + ( b * p + sum ) + ( c * p + sum )
        int ans = 0, sum = 0, p = 0;
        for(int n : nums) {
            sum += n;
            p += pow(10, countBits(n));
        }
        for(int n : nums) {
            ans += n * p + sum;
        }
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

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