Diameter in a binary tree

Problem

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

The length of the diamer of the binary tree can pass through the root of the binary tree or not.

In case that it passes.

The diameter is the height of the left subtree + the height of right subtree + 1 that is the root.

height of the left subtree + the height of right subtree + 1

is it not necesary that the path of the diameter passes throught the root.

In case that it dosn’t passes.

You need to calculate the diameter of the left and right subtree and the right subtree.

Now lets consider the new tree, for the new tree ldiameter will be the height of the left subtree. and repeat for rdiameter.

if it does not pass throught root we need to pass the left subtree and right subtree through the recursive function. and out of that leftsubtree and right rubstring reconsider the greater and pick that one.

height of the left subtree + the height of right subtree + 1,

max (ldiameter, rdiameter) )

you have to calculate both of this scenarios because we are not sure wheter or not we pass throught the root.

max(height of the left subtree + the height of right subtree + 1,

max (ldiameter, rdiameter) ))

solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        guard root != nil else{return 0}
        return diameter(root: root)
    }
    func diameter(root: TreeNode?) -> Int {
        guard root != nil else{return 0}
        var rootDiameter:Int = heightOfBinaryTree(root: root?.left) + heightOfBinaryTree(root: root?.right) + 1
        print("\(rootDiameter)")
        var leftDiameter:Int = diameter(root: root?.left)
        var rightDiameter:Int = diameter(root: root?.right)

        return max(rootDiameter, max(leftDiameter, rightDiameter))
    }
    
    func heightOfBinaryTree(root: TreeNode?) ->Int {
        if(root == nil){
            return 0
        }else{
            return max(heightOfBinaryTree(root: root?.left), heightOfBinaryTree(root: root?.left)) + 1
        }
    }
    
}

reference

https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/529/week-2/3293/

Best Time to Buy and Sell Stock II

I joined leet code 30 days of code challenge and this is the 5th challenge. I would like to give some of the insight I found while solving this problem with swift. The problem as follows.

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

The first approach consist in taking advantage of the moment we find a valley and immediately after take into account its adjacent peak. now we add the difference.

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count == 0 {return 0}
        var maxProfit: Int = 0
        var valley: Int = prices[0]
        var peak: Int = prices[0]
        var i: Int = 0
        print(prices.count)
        while i < prices.count - 1{
            while i < prices.count - 1  && prices[i] >= prices[i+1]{
                i += 1
            }
            print("this is  a valley \(prices[i]) ")
            valley = prices[i]
            
            while i < prices.count - 1 && prices[i] < prices[i+1]{
                i += 1
            }
            print("this is a peak \(prices[i])")
            peak = prices[i]
            
            maxProfit += peak - valley
        }
}

The second solution takes advantage of the fact that the sum of every incremental value can be uses to simulated the highest peak. So the sum of small increment A, B and C are equals to the largest increment to the peak.

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var diff: Int = 0
        if prices.count == 0 || prices.count == 1 {return 0}
        for i in 1...prices.count-1{
            print(i)
            if prices[i] > prices[i-1]{
                diff += prices[i] - prices[i-1]
            }
        }
        
        return diff
    }
}

different Rightmost Bit

You’re given two integers, n and m. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2^{position_of_the_found_bit} (0-based).

Example

For n = 11 and m = 13, the output should be
differentRightmostBit(n, m) = 2.11₁₀ = 1011₂, 13₁₀ = 1101₂, the rightmost bit in which they differ is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 2¹ = 2.
For n = 7 and m = 23, the output should be
differentRightmostBit(n, m) = 16.7₁₀ = 111₂, 23₁₀ = 10111₂, i.e.
```
00111
10111
```
So the answer is 2⁴ = 16.

int differentRightmostBit(int n, int m) {
  System.out.println(Integer.toBinaryString(n^m));
  System.out.println(Integer.toBinaryString((~(n^m))));

  return (~(n^m)+1)&(n^m);
}

this is a similar problem to the last bitwise problem I posted this week.

Turning all the different bits to 1 is straightforward with xor:
n XOR m
Turning all the bits to 0 is also straightforward with AND and NOT:
(n XOR m) AND (NOT(x XOR m))

if you n & ~n you get 0 but if you n & ~n+1 you get the first value that was 1.

https://catonmat.net/low-level-bit-hacks

Second rightmost zero

This is a problem excersice from codesignal platform.

problem

Presented with the integer n, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2^{position_of_the_found_bit}.

Example

For n = 37, the output should be
secondRightmostZeroBit(n) = 8.

37₁₀ = 100101₂. The second rightmost zero bit is at position 3 (0-based) from the right in the binary representation of n.
Thus, the answer is 2³ = 8.

answer:

/*
You have to get rid of the rightmost 0
To fill in the rightmost 0 with 1 using x | (x + 1)
    10111100  (x)
|   10111101  (x + 1)
    --------
    10111101
Isolate the new rightmost 0
To isolate it use ~x & (x + 1)
// now x is the value after step 1

    10111101  (x)
    --------
    01000010  (~x)
&   10111110  (x + 1)
    --------
    00000010
 in short 
  return ~(n|(n+1)) & ((n|(n+1))+1) ;
*/