The Fellow Programmer

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]; } } Try it on Leetcode 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

Problem Statement: Write a program to find a perfect square between 1 and 500 in C using while loop. HINT: A number is said to be perfect square if multiples of a number are same. eg., 16 is perfect square because it's multiples are 4 * 4.   #include <stdio.h> #include <math.h> int main() {     int start=1;    while(start<500){ //change 500 to any n        if (sqrt(start) == (int)sqrt(start)) {            printf("%d ",start);        }        start++;    }     return 0; } Run above code now Here we are going to solve using sqrt() in <math.h>. sqrt() returns double value. (int)sqrt() returns int value. If both float and int are same, then it is a perfect square. [i.e., 4.0 == 4] and print that number. You can also increase upto any number only by changing condition in While loop[which is mentioned as comment]. Subscribe us to receive updates instantly. Please let us know about your views