Vpropel VIT | POD | 13/05/2020 | Squares | 04

Question(Squares).txt

Squares
Every number can be expressed as sum of perfect squares. 

For example

1= 1 

So number of perfect squares required 1

2=1+1 

So number of perfect squares required 2

3= 1+1+1 

So number of perfect squares required 3

4=4 

So number of perfect squares required 1

5=1+4 

So number of perfect squares required 2

6=4+1+1 

So number of perfect squares required 3

12=4+4+4 

So number of perfect squares required 3 

101=100+1

So number of perfect squares required 2

Given number n find the least number of perfect squares required to represent the sum

Input format:-

Number-N

Output format:-

Minimum number of perfect squares required.

Constraints

1<=N<=2*106

Rank.txt

1	19BCE1401	S VAIBHAVE
2	19BLC1055	SUNIL KUMAR GV
3	19BCE1025	NAMAN KUMAR SINGH
4	19BCI0016	CHIRANJEET SINGH
5	19BCE1773	PRIYA
6	19BEC1212	SUJITH K P
7	19BCE1376	VIKASH SUNIL
8	19BCE0905	KANHAIYA KUMAR
9	19BEC1291	MAYANK VERMA
10	19BAI1151	PRANAV BALAJI

squares.cpp

#include<iostream>
#include<cmath>
#include<algorithm>

int minSqT(int n)
{
   int sqList[n+1]={0};  //sqList[0]=0 (no need to specify, as already whole array is '0')
   for (int i = 1; i <= n; i++) 
   {
        sqList[i] = i;
        for (int x = 1; x <= int(sqrt(i)); x++)
            sqList[i] = std::min(sqList[i], 1+sqList[i-int(pow(x,2))]);
   }
   return sqList[n];
}
int main() 
{
   int n;
   std::cin >> n;
   std::cout <<minSqT(n);
   return 0;
}

squares.java

import java.util.Scanner;
class MinRecurs
{
    public static int NumSq(int n)
    {
        int SqList[]=new int[n+1];
        for(int i=1;i<=n;i++)
        {
            SqList[i]=i;
            for(int j=1;j<=(int)Math.sqrt(i);j++)
            {
                SqList[i]=Math.min(SqList[i],1+SqList[i-j*j]);    
            }
        }
        return SqList[n];
    }
}
public class Main
{
    public static void main(String[] args)
    {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        System.out.print(MinRecurs.NumSq(n));
    }
}

squares.py

import math
n=int(input())
l=[0]*(n+1)
for i in range(1,n+1):
    l[i]=i
    for j in range(1,int(math.sqrt(i))+1):
        l[i]=min(l[i],1+l[i-j*j])
print(l[n])

squares2.java

// Don't ever use this approach. See squares.java
// Exponential time complexity. See Recursive approach (Squares.java), for resque. That has quadratic time complexity
import java.util.Scanner;
class MinRecurs
{
    public static int NumSq(int n,int opt)
    {
        if(n<=0)
            return 0;
        int min=NumSq(n-1*1,opt);
        for(int i=2;i<=opt && i*i<=n;i++)
        {
            min=Math.min(min,NumSq(n-i*i,opt));
        }
        return min+1;
    }
}
public class Main
{
    public static void main(String[] args)
    {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int opt=(int)Math.sqrt(n);
        System.out.print(MinRecurs.NumSq(n,opt));
    }
}