Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
 class Solution {
    public int numSquares(int n) {
   int[] dp = new int[n + 1];
    int near, min;
    for (int i = 1; i <= n; i++) {
        near = (int) Math.sqrt(i);
         min = dp[i - 1];
        for (int j = near; j > 0; j--) {
                min = Math.min(dp[i - j * j], min);
        }
        dp[i] = min + 1;
    }

    return dp[n];
}
}


Here, we are going to solve problem using bottom up DP(Dynamic Programming).

1) Initialize dp array having size of n+1.
2) i variable iterates from 1 to n and for each i values we find nearest square number (near variable).
3) j iterates from near to 1 and for each j value we find Math.min(dp[i - j * j], min) . After finding min value, store dp[i] as min+1.
4) Finally, dp[n] contains minimum number of perfect square sum to reach n.

[NOTE]If you take any n, dp[0] to dp[4] have same values.

Consider following example,

For n = 6, O/P is 3 (i.e 1+1+4)

i=1,             i=2,            i=3,              i=4,            i=5               i=6
near =1      near = 4       near = 9      near = 16    near = 25      near = 36
min = 0      min = 1       min = 2       min = 3       min = 1        min = 2
dp[1]= 1     dp[2] = 2     dp[3] = 3    dp[4] = 4     dp[5] = 2     dp[6] = 3


Click Follow button to receive updates from us instantly.

Please let us know about your views in comment section.

                                                        😍..Happy Coding...😍
The intention behind this blog is to help all my fellow programmers. Also to provide solutions for various coding platform problems with solution and explanation. I will add many tutorials in future. I am not a professional blogger but whenever time permits I will post. I hope you’ll enjoy the content and find it useful! Check out my Writer blog for a more valuable quotes. For any queries or suggestions, please feel free to reach out to me. Happy coding!

Comments

Post a Comment

Popular posts from this blog

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contain only lowercase letters. class Solution {     public int firstUniqChar(String s) {         int length = s.length();         String str;         for(int i=0;i<length;i++){             if(i==length-1){                 str = s.substring(0, i);             }             else{                 str = s.substring(0,i)+s.sub...
Read more

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of  every  node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true   Constraints: The number of nodes in the tree is in the range  [0, 5000] . -10 4  <= Node.val <= 10 4 Solution: /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int ...
Read more

Majority Element

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. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2   class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } Here, we are sorting the entire array using sort() of Arrays class. Then, number at index position n/2 would be a majority element. There is no chance of wrong values in odd or even length.   Below is another method using HashMap. METHOD 2: class Solution { public int majorityElement(int[] nums) { HashMap<Integer, Integer>list = new HashMap<Integer, Integer>(); int ...
Read more

Sequential Digits

An integer has sequential digits if and only if each digit in the number is one more than the previous digit. Return a sorted list of all the integers in the range [low, high]  inclusive that have sequential digits. Example 1: Input: low = 100, high = 300 Output: [123,234] Example 2: Input: low = 1000, high = 13000 Output: [1234,2345,3456,4567,5678,6789,12345] Constraints: 10 <= low <= high <= 10^9 class Solution {     public List<Integer> sequentialDigits(int low, int high) {         List<Integer> result = new ArrayList();         String str = "123456789";         int i, j, length = str.length(), num;         for( i = 2; i <= length; i++) {             for( j = 0; j <= length - i; j++) {      ...
Read more