leetcode Largest Divisible Subset

leetcode Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj% Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Example 2:

leetcode Valid Perfect Square

leetcode Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as `sqrt`.

Example 1:

Example 2:

leetcode Water and Jug Problem

leetcode Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

Operations allowed:

• Fill any of the jugs completely.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

Example 2:

leetcode Count Numbers with Unique Digits

leetcode Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding `[11,22,33,44,55,66,77,88,99]`)

leetcode Power of Four

leetcode Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

leetcode Counting Bits

leetcode Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For `num = 5` you should return `[0,1,1,2,1,2]`.

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

leetcode House Robber III

leetcode House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

leetcode Self Crossing

leetcode Self Crossing

You are given an array x of `n` positive numbers. You start at point `(0,0)` and moves `x[0]` metres to the north, then `x[1]` metres to the west,`x[2]` metres to the south, `x[3]` metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with `O(1)` extra space to determine, if your path crosses itself, or not.

Example 1:
Given x = `[2, 1, 1, 2]`
Return `true` (self crossing)
Example 2:
Given x = `[1, 2, 3, 4]`
Return `false` (not self crossing)
Example 3:
Given x = `[1, 1, 1, 1]`
Return `true` (self crossing)

leetcode Increasing Triplet Subsequence

leetcode Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < kn-1 else return false.Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given `[1, 2, 3, 4, 5]`,
return `true`.

Given `[5, 4, 3, 2, 1]`,
return `false`.

leetcode Verify Preorder Serialization of a Binary Tree

leetcode Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as `#`.

For example, the above binary tree can be serialized to the string `"9,3,4,#,#,1,#,#,2,#,6,#,#"`, where `#` represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character `'#'` representing `null` pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as `"1,,3"`.