Sum of cubes

How can I solve this?

Please,Help

It’s very similar to finding the numbers in an array of cubes of 1 to 9 whose sum is equal to n. Bruteforcing with recursion can be used here, given that the size of array is only 9 here.

Code?

@vusetorucov You will be able to make every possible number with sum of cube of digits. A little prove for this is suppose you want to make number N so , you make number such as 11111…upto N times , sum of cubes of its digit will be N . But we want minimum possible number.

so we can check if N is less then cube of any number between 9 to 1 ( subtracting max possible cube in each iteration will give minimum possible number that why we start iterating from 9 not 1 ) , we always get a digit from here if n != 0 so we add that digit to our answer vector and repeat following process until n becomes 0. Finally we will reverse our answer vector to get smallest permeation of number.

```
#include<bits/stdc++.h>
using namespace std ;
int main()
{
int n ;
cin >> n ;
vector< int > ans ;
i = 9 ;
while( n )
{
while( i*i*i <= n )
{
ans.push_back( i ) ;
n -= ( i*i*i) ;
}
i-- ;
}
reverse(ans.begin(),ans.end()) ;
for( auto i : ans )
cout << i ;
return 0 ;
}
```

This code:

n=1024

return 11111112469

but ans=88

Sorry for the late reply. It’s in Java but working for me…

```
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
static BufferedReader br;static PrintWriter pr;
static long solve(int n,int[] left,String[] res){
boolean flag=true;
int le=left.length-1;
while(flag){
for(int j=1;j<=le;j++){
for(int k=j;k>=1;k--){
if(k*k*k<=left[j]){
left[j]-=k*k*k;
res[j]+=k;
break;
}
}
if(left[j]==0) flag=false;
}
}
long minno=Long.MAX_VALUE;
for(int i=1;i<=le;i++){
if(left[i]==0){
PriorityQueue<Integer> pq=new PriorityQueue<>();
for(int j=0;j<res[i].length();j++) pq.add(res[i].charAt(j)-'0');
long m=0;
while(!pq.isEmpty()) m=m*10+pq.poll();
minno=minno<m?minno:m;
}
}
return minno;
}
static void testcase()throws java.lang.Exception{
int n=Integer.parseInt(br.readLine()); int i;
for(i=1;i<=9;i++){
if(i*i*i>n) break;
}
int[] left=new int[i]; Arrays.fill(left,n);
String[] res=new String[i]; Arrays.fill(res,"");
pr.println(solve(n,left,res));
}
public static void main (String[] args) throws java.lang.Exception
{
br = new BufferedReader(new InputStreamReader(System.in));
pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
testcase();
pr.close();
}
}
```

Runtime error

On what value?

runtime error

I really don’t know where’s that error coming from. In Ideone, there’s no runtime error, but in vjudge, it’s showing it. Don’t know how they’re running this code…

@vusetorucov I was really going greedy and missed this so from here we have to check all possible numbers cube of whose digits sums to N. For Optimization DP can be used here.

For that go through this , Minimum number of cubes whose sum equals to given number N

Thanks a lot.