coin problem(giving result for small no.s but in question if no. is 1000000000 then not able to define array of that or n/4 length)

[vineet gandhi]

import java.util.Scanner;

/**
*
* @author roger
*/
public class Main {
static int arr[]=new int[1000000];
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner s=new Scanner(System.in);

int x = s.nextInt();
for(int i=0;i<x;i++)
{int a=s.nextInt();
int z= func(a);
System.out.println(z);
}

}
static int func(int q)
{if(q<12)
{
return q;
}
if(arr[q]==0)
{
arr[q]=func(q/2)+func(q/3)+func(q/4);

}
return arr[q];
}

}

[Navin Agarwal]

You need to use some data structure like map in c++, for storing the values.


--
Navin Agarwal

[anoop chaurasiya]

@vineet, as the constraints don't allow u to use the complete memoisation, u may use memoisation up to some extent and recalculate if the numbers are too big...here is the idea...

#define MAX 10000000

int best[MAX]={-1};

int calc(int n)

{

if(n<MAX)

{

if(already calculated)

return best[n];

else

best[n]=/* calculate best */;

}

return /*calc best*/;

}

--
Anoop Chaurasiya
CSE (2008-2012)
NIT DGP

[vineet gandhi]

thanks a lot!!!


On Mar 13, 6:45 am, anoop chaurasiya <anoopchaurasi...@gmail.com>
wrote:

> NIT DGP- Hide quoted text -
>
> - Show quoted text -

[Manish Agrahari]

As mailed by Navin, Today (Monday) there is class of Algo. The topic for today is

1)Bitset and its application
2)Some interesting problems.


        Time    :    6:00 pm
        Date     :    14th March
        Venue   :    D.M.Sen Complex

This'll be taken by Anoop, Navin.

@vineet ,abhishek ,shalini please inform to your branch-mates for this class through respective groups..

Thanks

--
Manish Kumar Agrahari
CSE :: 3rd year
National Institute of Technology,
Durgapur