K Factorization

Problem Statement :

At the time when Pythagoreanism was prevalent, people were also focused on different ways to factorize a number. In one class, Pythagoras asked his disciples to solve one such problem, Reverse Factorization. They were given a set of integer, , and an integer . They need to find the a way to reach , starting from , and at each step multiplying current value by any element of . But soon they realised that there may exist more than one way to reach . So they decided to find a way in which number of states are least. All of sudden they started on this new problem. People solved it and then started shouting their answer. CRAP!!!. There still exists multiple answers. So finally after much consideration, they settled on the lexicographically smallest series among those solutions which contains the least number of states.


Here (a) is not the minimal state, as it has  states in total. While (b) and (c) are contenders for answer, both having 3 states, (c) is lexicographically smaller than (b) so it is the answer. In this case you have to print 1 3 12. If there exists no way to reach  print -1.

Input Format

Input contains two lines where first line contains two space separated integer,  and , representing the final value to reach and the size of set , respectively. Next line contains K space integers representing the set .


Output Format

Print the steps to reach N if it exists. Otherwise print -1.

Solution :

                            Solution in C :

In C  :







#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void calculate ( long target, long *a, long a_len, long *v ) {
  long x,y,rv;
  for (x=0;x<a_len;x++) {
    if (target==a[a_len-1-x]) {
      v[0] = a[a_len-1-x];
      v[1] = 0;
      return;
    } else if ((target%a[a_len-1-x])==0) {
      calculate(target/a[a_len-1-x],a,a_len,v);
      y=0; while(v[y]!=0) { y++; } v[y]=a[a_len-1-x]; v[y+1]=0;
      return;
    }
  }

}

void local_sort ( long *v, long v_len ) {
  long x,y,temp;
    
  for (x=1;x<v_len;x++) {
    y=x-1; while ((y>=0)&&(v[x]<v[y])) { y--; }
    temp = v[x];
    if (v[x]<v[y]) {
      memmove(&(v[y+1]),&(v[y]),(x-y)*sizeof(long));
      v[y] = temp;
    } else if (y<x-1) {
      memmove(&(v[y+2]),&(v[y+1]),(x-y)*sizeof(long));
      v[y+1] = temp;
    }
  }
  return;
}


int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long V,N,*a,x,ans,pos;
    long *sol;
    
    sol = (long *)malloc(64*sizeof(long));
    memset(sol,0,64*sizeof(long));
    
    scanf("%ld %ld\n",&V,&N);
    a = (long *)malloc(N*sizeof(long));
    pos = 0;
//printf("READ: ");
    for (x=0;x<N;x++) {
      scanf("%ld",&(a[pos]));
//printf("%ld (%ld),",a[pos],V%a[pos]);        
      if ((V%a[pos])==0) {
        pos++;
      }
    }
//printf("\n");
    
//printf("DIVISIBLE: "); for (x=0;x<pos;x++) { printf("%ld ",a[x]); } printf("\n");
    
    local_sort(a,pos);

//printf("SORT: "); for (x=0;x<pos;x++) { printf("%ld ",a[x]); } printf("\n");

    calculate(V,a,pos,sol);
//printf("SOLUTION:\n");
    
    x=0;
    ans = 1;
    while (sol[x]!=0) { ans *= sol[x]; x++; }
    
    if (ans==V) {
      x=0;
      ans = 1;
      printf("%ld ",ans);
      while (sol[x]!=0) {
        ans *= sol[x];
        printf("%ld ",ans); x++;
      }
      printf("\n");
    } else {
      printf("-1\n");
    }
    
    return 0;
}

                        Solution in C++ :

In  C++  :






#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

bool isLess(const vector<uint32_t>& left, const vector<uint32_t>& right){
	if (left.size() != right.size()) return left.size()<right.size(); 
	for(int i=0; i<left.size(); i++){
		if (left[i]!=right[i]) return left[i]<right[i]; 
	}
	return false; 
}

bool eval(const uint32_t N, const vector<uint32_t>& vals, 
	vector<uint32_t>& answer, vector<uint32_t> current){
	if (N==1){
		sort(current.begin(), current.end()); 
		if (answer.empty()) answer = current; 
		else if (isLess(current, answer)) answer.swap(current); 
		return true; 
	}
	if (answer.size()>0 && current.size()>=answer.size()) return false; 
	bool retval = false; 
	for(int i=vals.size()-1; i>=0; i--){
		if (vals[i]<=N && (N%vals[i])==0){
			current.push_back(vals[i]); 
			retval |= eval(N/vals[i], vals, answer, current); 
		}
	}
	return retval; 
}

int main(void){
	uint32_t N; 
	cin >> N; 	// 1 - 1,000,000,000
	int K; 
	cin >> K; // 1 - 20
	vector<uint32_t> vals(K); 
	for(int i=0; i<K; i++) cin >> vals[i]; // each 2 - 20 and distinct
	sort(vals.begin(), vals.end()); 

	vector<uint32_t> answer, temp; 
	if (eval(N, vals, answer, temp)){
		uint32_t v = 1; 
		cout << v << " "; 
		for(int i=0; i<answer.size(); i++){
			v *= answer[i]; 
			cout << v << " "; 
		}
		cout << endl; 
	} else {
		cout << -1 << endl; 
	}
	return 0; 
}

                        Solution in Java :

In  Java :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int c = s.nextInt();
        
        int[] arr = new int[c];
        for(int i=0; i<c; i++) {
            arr[i] = s.nextInt();
        }
        String out = cal(arr, n, 0, "" + n, new String[1] );
        System.out.println(out == null ? -1 : out);
    }
    
    static String cal(int[] arr, int result, int step, String output, String[] strs) {
        if(strs[0] != null && strs[0].length() < output.length()) {
            return null;
        }
        
        if(result == 1) {
            strs[0] = output;
            return output; 
        } 
        
        String out = null;
        for(int i = 0; i<arr.length; i++) {
            if(result % arr[i] ==0) {
                String temp = cal(arr, result / arr[i], step + 1,result / arr[i] + " " + output, strs);
                if(temp == null) {
                    continue;
                } else if(out == null) {
                    out = temp;
                } else {
                    out = out.length() < temp.length() ? out : temp;
                }
            }
        }
        
        return (out == null) ? null : out;
    }
}

                        Solution in Python : 
                            
In  Python3 :






def getResult(n, a):
    
    if n is 1:
        return []
    
    for x in a:
        if n % x is 0:
            break
    else:
        return False
    
    for x in a:
        if n % x is 0:
            result = getResult(int(n/x), a)
            # print("result is ", result, "for", n/x, "with", a)
            if result is not False:
                result.append(x)
                return result

    return False

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

result = getResult(n, a)
if result is False:
    print(-1)
else:
    current = 1
    print(current, end=' ')
    for x in result:
        current *= x
        print(current, end=' ')

View More Similar Problems

Waiter

You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the

View Solution →

Queue using Two Stacks

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed. A basic que

View Solution →

Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

View Solution →

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

View Solution →

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

View Solution →

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

View Solution →

Our Effort to provide you the best solutions requires some appreciation

Please disable your adblocker and refresh

K Factorization

Problem Statement :

Solution :

View More Similar Problems

Waiter

Queue using Two Stacks

Castle on the Grid

Down to Zero II

Truck Tour

Queries with Fixed Length