K-Factorization
Problem statement: https://www.hackerrank.com/challenges/k-factorization. The most annoying part of this problem is the "sorting in lexicographic order", which is the code in the base case. Some string manipulation and calculation block according to the definition of lexicographic order in the problem statement is necessary. Rest of the code is an immediate brute-force using Depth-First-Search (DFS) approach. My first implementation was failing due to stack-overflow: changing the data types from Int32 to Int64 solved that problem. The second implementation was timing out: adding a "current index" to the function and starting the loop from that index (instead of starting from zero) did the job. Code is down below. May your week be awesome, folks!!! Also, see a pic of me and a bunch of kids watching #bossbaby today. Bye!!! Marcelo.
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(String[] args)
{
string[] parts = Console.ReadLine().Split(' ');
int n = Int32.Parse(parts[0]);
long k = Int32.Parse(parts[1]);
long[] numbers = new long[k];
parts = Console.ReadLine().Split(' ');
for (int i = 0; i < k; i++)
{
numbers[i] = Int32.Parse(parts[i]);
}
string bestSequence = "";
Process(n, k, numbers, 0, 1, "1", ref bestSequence);
if(bestSequence != "")
{
string[] solutionParts = bestSequence.Split(new char[] { '@' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < solutionParts.Length; i++)
{
Console.Write("{0} ", solutionParts[i]);
}
}
else
{
Console.WriteLine("-1");
}
}
static void Process(int n,
long k,
long[] numbers,
int currentIndex,
long currentProduct,
string currentSequence,
ref string bestSequence)
{
if (currentProduct > n)
{
return;
}
else if (currentProduct == n)
{
string[] currentSequenceParts = currentSequence.Split(new char[] { '@' }, StringSplitOptions.RemoveEmptyEntries);
string[] bestSequenceParts = bestSequence.Split(new char[] { '@' }, StringSplitOptions.RemoveEmptyEntries);
if (bestSequence == "" || currentSequenceParts.Length < bestSequenceParts.Length)
{
bestSequence = currentSequence;
}
else if(currentSequenceParts.Length == bestSequenceParts.Length)
{
int indexCurrent = currentSequenceParts.Length - 1;
int indexBest = bestSequenceParts.Length - 1;
while (indexCurrent >= 0 && indexBest >= 0)
{
long current = Int64.Parse(currentSequenceParts[indexCurrent]);
long best = Int64.Parse(bestSequenceParts[indexBest]);
if (current < best)
{
bestSequence = currentSequence;
break;
}
else if (best < current)
{
break;
}
indexCurrent--;
indexBest--;
}
}
return;
}
for (int i = currentIndex; i < k; i++)
{
if (currentProduct * numbers[i] <= n)
{
Process(n, k, numbers, i, currentProduct * numbers[i], currentSequence + "@" + (currentProduct * numbers[i]).ToString(), ref bestSequence);
}
else
{
break;
}
}
}
}
here is how I read the problem:
ReplyDeleteblah blah... a way to reach (so graph traversal), blah blah... least (so BFS), blah blah... lexicographically smallest (so sort).
http://ideone.com/ZjfzFY
#include
#include
#include
#include
#include
#include
using namespace std;
void print_path(int num, const unordered_map &parent) {
vector path;
do {
path.push_back(num);
num = parent.at(num);
} while (num != -1);
copy(path.rbegin(), path.rend(), ostream_iterator(cout, " ")); cout << endl;
}
int main() {
int n, k; cin >> n >> k;
vector factors(k);
for (int i = 0; i < k; ++i) cin >> factors[i];
sort(factors.begin(), factors.end());
queue q;
q.push(1);
unordered_map parent;
parent[1] = -1;
while (!q.empty()) {
int num = q.front(); q.pop();
for (int factor : factors) {
int next = num * factor;
if (next > n) break;
if (parent.count(next)) continue;
parent[next] = num;
if (next == n) {
print_path(next, parent);
return 0;
}
q.push(next);
}
}
cout << "-1" << endl;
return 0;
}
I love these types of problems! Thanks for sharing, Marcelo!