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 (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:

Factorial of a No. using Dynamic Programming

 Following program show how to find out the factorial of a No. using Dynamic Programming.

Factorial of No.   :
 
class Factorial
{
  public static void main(String[] args) {
    int n=8;
    long arr[] = new long[n+1];
    for(int i=0 ;i<n+1;i++)
      arr[i]=0L;
    System.out.println("Factorial is :: "+fact(n,arr));
  }
  static long fact(int n, long arr[])
  {
    if (n==0 || n==1)
      return 1;
    else if(arr[n]!=0)
      return arr[n];
    else
      {
        arr[n]=fact(n-1, arr)*n;
        return arr[n];
      }
  }
}