# Posts published in “Easy”

Problem:

self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Note:

• The boundaries of each input argument are 1 <= left <= right <= 10000.

Idea:

Brute Force

Time Complexity: O(n)

Space Complexity: O(1)

Solution:

C++

String

Related Problems:

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Example 2:

Note:

• All the strings in the input will only contain lowercase letters.
• The length of words will be in the range [1, 1000].
• The length of words[i] will be in the range [1, 30].

Idea:

Brute force

Trie

Solution:

C++

Trie + Sorting

Trie + No sorting

Problem:

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Example 2:

Note:

• The length of nums will be in the range [0, 10000].
• Each element nums[i] will be an integer in the range [-1000, 1000].

Idea:

DP

Solution:

C++

Java

Python

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:

Solution 1:

Hash table O(n) / O(n)

Solution 2:

BST O(nlogk) / O(n)

Solution 3:

Randomization O(n) / O(1)

Solution 4:

Bit voting O(n) / O(1)

Solution 5:

Moore Voting O(n) / O(1)

Solution 6:

Full sorting O(nlogn) / O(1)

Solution 7:

Partial sorting O(n) / O(1)

Solution 8:

Divide and conquer O(nlogn) / O(logn)

Divide and conquer O(nlogn) / O(logn)

Mission News Theme by Compete Themes.