K Factorization – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#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;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[k];
for(int i = 0; i < k; i++) {
a[i] = sc.nextInt();
}
LinkedList<Integer> sol = new LinkedList<Integer>();
Arrays.sort(a);
if(backtrack(n,a,a.length-1,sol)) {
int curr = 1;
for(int i = 0; i < sol.size()-1; i++) {
curr *= sol.get(i);
System.out.print(curr + " ");
}
curr *= sol.get(sol.size()-1);
System.out.println(curr);
} else {
System.out.println(-1);
}
}
public static boolean backtrack(int n, int[] a, int index,LinkedList<Integer> sol) {
if(n == 1) {
sol.add(1);
return true;
}
for(int i = index; i >= 0; i--) {
if(n % a[i] == 0) {
if(backtrack(n/a[i],a,i,sol)) {
sol.add(a[i]);
return true;
}
}
}
return false;
}
}
Python 3 rep HackerRank Solution
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=' ')
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
n, k = map(int, raw_input().split() )
a = [int(c) for c in raw_input().split()]
a.sort()
a.reverse()
def find_factor(n, A):
sol = []
for i in range(len(A)):
if n==A[i]:
sol.append([A[i]])
elif n%A[i]==0:
tmp = find_factor(n/A[i], A[i:])
if len(tmp) > 0:
sol.append([A[i]] + tmp)
#print "solutions for %d : %s" %(n, str(sol))
if len(sol) == 0:
return []
minimum_length = min([len(s) for s in sol])
sol = [s for s in sol if len(s) == minimum_length]
#print sol
sol.sort(key=lambda x:x[0])
return sol[-1]
res = find_factor(n,a)
res.reverse()
res2 = [1]
for r in res:
res2.append(res2[-1]*r)
if not res2[-1] == n:
print -1
else:
print " ".join([str(i) for i in res2] )
C rep HackerRank Solution
#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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below