Sunday 26 December 2021

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:

1641. Count Sorted Vowel Strings

 Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid is[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:

Saturday 25 December 2021

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.

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 :


392. Is Subsequence

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

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 :

Tuesday 8 November 2016

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)