@Don, amazing solution.
Let us say, I don't have the insight to see the greedy solution mentioned
by @Don there is an obvious dp solution for the general case.
typedef long long int64;
const int64 LINF = (int64) 1e16 + 5;
map <int64, int64> memo;
int64
solve (int n) {
if (n < 10) return n;
if (memo.count (n)) return memo [n];
int64 ret = LINF;
for (int i = 9; i >= 2; i--)
if (n % i == 0)
ret = min (ret, 10 * solve (n / i) + i);
return memo [n] = ret;
}
int
main () {
#ifdef LOCALHOST
freopen ("test.in", "r", stdin);
// freopen ("test.out", "w", stdout);
#endif
int n = 100;
int64 ret = solve (n);
if (ret >= LINF) ret = -1; // Solution does not exist.
return 0;
}
This solution won't work when result exceed 64 bit integers but can easily
be
modified to work with strings.
On Thu, Feb 13, 2014 at 5:57 PM, bhargav <[email protected]> wrote:
> import java.util.ArrayList;
>> import java.util.Collections;
>> import java.util.List;
>> import java.util.Scanner;
>>
>>
>> public class PrimeFactors {
>>
>> /**
>> * @param args
>> */
>> public static void main(String[] args) {
>> Scanner sc = new Scanner(System.in);
>> int n = sc.nextInt();
>> List<Integer> counts = new ArrayList<Integer>();
>> List<Integer> l = new ArrayList<Integer>();
>> l.add(2);
>> l.add(3);
>> l.add(5);
>> l.add(7);
>> for(int i=0;i<l.size();i++) {
>> int j=0;
>> while(n%l.get(i)==0) {
>> n = n/l.get(i);
>> j++;
>> }
>> counts.add(j);
>> }
>> if(n!=1) {
>> System.out.println(-1);
>> }
>> else {
>> System.out.println(counts);
>> System.out.println(generateComb(counts));
>> }
>> }
>> public static int generateComb(List<Integer> l) {
>> List<Integer> li = new ArrayList<Integer>();
>> int temp=0;
>> for(int i=0;i<l.size();i++) {
>> int k = 0;
>> int j =0;
>> if(l.get(i)==0&&temp==1&&i==1) {
>> li.add(2);
>> }
>> if(l.get(i)==0) {
>> continue;
>> }
>> switch (i) {
>> case 0: k = l.get(i)%3;
>> if(k!=l.get(i)) {
>> j = l.get(i)/3;
>> while(j!=0) {
>> li.add(8);
>> j--;
>> }
>> }
>> if(k==2)
>> li.add(2*k);
>> temp=k;
>> break;
>> case 1: k = l.get(i)%2;
>> if(k!=l.get(i)) {
>> j = l.get(i)/2;
>> while(j!=0) {
>> li.add(9);
>> j--;
>> }
>> }
>> if(temp==1&&k==1) {
>> li.add(6);
>> }
>> else if(k==1) {
>> li.add(3);
>> }
>> else if(temp==1) {
>> li.add(2);
>> }
>> break;
>> case 2: k = l.get(i);
>> while(k!=0) {
>> li.add(5);
>> k--;
>> }
>> break;
>> case 3: k = l.get(i);
>> while(k!=0) {
>> li.add(7);
>> k--;
>> }
>> break;
>> }
>> }
>> Collections.sort(li);
>> return generateNumFromArray(li);
>> }
>> public static int generateNumFromArray(List<Integer> l) {
>> int num=0;
>> for(int i=0;i<l.size();i++) {
>> num = num*10 + l.get(i);
>> }
>> return num;
>> }
>> }
>>
>
> btw was this from interviewstreet interview ?? :P
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
