1277. Count Square Submatrices with All Ones

 Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

 

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

 

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Solution:

	class Solution(object):
	def countSquares(self, matrix):
	"""
	:type matrix: List[List[int]]
	:rtype: int
	"""
	m,n = len(matrix),len(matrix[0])
	for i in range(1,m):
	for j in range(1,n):
	if matrix[i][j]==1:
	matrix[i][j] = 1+min([matrix[i][j-1],matrix[i-1][j],matrix[i-1][j-1]])
	s = 0
	for i in range(m):
	for j in range(n):
	s+=matrix[i][j]
	return s

view raw count-square-submatrices-with-all-ones.py hosted with ❤ by GitHub

1641. Count Sorted Vowel Strings

 Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

 

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

 

Constraints:

• 1 <= n <= 50 

Solution:

	class Solution(object):
	def countVowelStrings(self, n):
	"""
	:type n: int
	:rtype: int
	"""
	dp ={}
	def cv(i,vowels):
	if i in dp and vowels in dp[i]:
	return dp[i][vowels]
	if i==1:
	return vowels
	if vowels ==1:
	return 1
	if i not in dp:
	dp[i]=dict()
	dp[i][vowels]=cv(i-1,vowels)+cv(i,vowels-1)
	return dp[i][vowels]
	return cv(n,5)

view raw count-sorted-vowel-strings.py hosted with ❤ by GitHub

894. All Possible Full Binary Trees

 Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

 

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

 

Constraints:

• 1 <= n <= 20

Solution :

	class Solution(object):
	dp = {0:[],1:[TreeNode(0)]}
	def allPossibleFBT(self, n):
	if n in Solution.dp:
	return Solution.dp[n]
	ans = []
	for i in range(n):
	j = n-1-i
	for l in self.allPossibleFBT(i):
	for r in self.allPossibleFBT(j):
	bns = TreeNode(0)
	bns.left = l
	bns.right = r
	ans.append(bns)
	Solution.dp[n]=ans
	return ans

view raw all-possible-full-binary-trees.py hosted with ❤ by GitHub

392. Is Subsequence

 Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

 

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

 

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 104
• s and t consist only of lowercase English letters.

Solution :

	class Solution(object):
	def isSubsequence(self, s, t):
	"""
	:type s: str
	:type t: str
	:rtype: bool
	"""
	sb,tb=len(s),len(t)
	i,j=0,0
	while i<sb and j<tb:
	if s[i]==t[j]:
	i+=1
	j+=1
	return i==sb

view raw is-subsequence.py hosted with ❤ by GitHub

Hackerrank , Project Euler #5: Smallest multiple

Project Euler #5: Smallest multiple

from fractions import gcd

def lcm(numbers):

    return reduce(lambda x, y: (x*y)/gcd(x,y), numbers)

t=input()

for i in range(0,t):

    print lcm(range(1,input()+1))

Hackerrank , Project Euler #4: Largest palindrome product

Project Euler #4: Largest palindrome product

# Enter your code here. Read input from STDIN. Print output to STDOUT
t=input()
for i in range(0,t):
    no=input()
    for k in range(no-1,101100,-1):
        if str(k)==str(k)[::-1]:
            lst = [k for e in range(100,999) if k%e==0 and len(str(k/e))==3]
            if lst :
                print max(lst)
                break

Hckerrank , Project Euler #3: Largest prime factor

Project Euler #3: Largest prime factor

# Enter your code here. Read input from STDIN. Print output to STDOUT

t=input()

def largest_prime_factor(n):

    i = 2

    while i * i <= n:

        if n % i:

            i += 1

        else:

            n //= i

    return n

for j in range(0,t):

    n=input()

    print largest_prime_factor(n)