Dijkstra, Miller-Rabin and Caching
This problem requires Dijkstra since it is a Breadth-First Search (BFS) but you always want to dequeue the element with the smallest path-sum first, hence instead of using a queue you'll need to use a priority queue. It also has a twist that it requires you to check for prime numbers along the way. My favorite method (although overkill here) is Miller-Rabin, but even Miller-Rabin leads to Time Limit Exceeded (TLE) hence you'll need to combine it with global caching. HashSet performs better than HashTable from my observation. Even with all that in place, it was still leading to TLE. Reducing the size of the priority queue from 20K to 10K did the trick. Code is down below. Greetings from the Big Island!! ACC.
Digit Operations to Make Two Integers Equal - LeetCode
You are given two integers n and m that consist of the same number of digits.
You can perform the following operations any number of times:
- Choose any digit from
nthat is not 9 and increase it by 1. - Choose any digit from
nthat is not 0 and decrease it by 1.
The integer n must not be a prime number at any point, including its original value and after each operation.
The cost of a transformation is the sum of all values that n takes throughout the operations performed.
Return the minimum cost to transform n into m. If it is impossible, return -1.
Example 1:
Input: n = 10, m = 12
Output: 85
Explanation:
We perform the following operations:
- Increase the first digit, now
n = 20. - Increase the second digit, now
n = 21. - Increase the second digit, now
n = 22. - Decrease the first digit, now
n = 12.
Example 2:
Input: n = 4, m = 8
Output: -1
Explanation:
It is impossible to make n equal to m.
Example 3:
Input: n = 6, m = 2
Output: -1
Explanation:
Since 2 is already a prime, we can't make n equal to m.
Constraints:
1 <= n, m < 104nandmconsist of the same number of digits.
public class Solution {
public static HashSet millerRabinCache = new HashSet();
public int MinOperations(int n, int m)
{
if (IsPrimeMillerRabin(n)) return -1;
PriorityQueue pQueue = new PriorityQueue(true, 10000);
HashSet visited = new HashSet();
NumberAndSumPath node = new NumberAndSumPath(n, n);
pQueue.Enqueue(node, node.sumPath);
visited.Add(n);
while (pQueue.Count > 0)
{
double tempPriority = 0;
NumberAndSumPath current = (NumberAndSumPath)pQueue.Dequeue(out tempPriority);
if (current.number == m)
{
return current.sumPath;
}
StringBuilder str = new StringBuilder(current.number.ToString());
//Decrease
for (int i = 0; i < str.Length; i++)
{
if (str[i] != '0')
{
char temp = str[i];
str[i] = (char)((int)str[i] - 1);
int nTemp = Int32.Parse(str.ToString());
if (!visited.Contains(nTemp) && !IsPrimeMillerRabin(nTemp))
{
NumberAndSumPath newNode = new NumberAndSumPath(nTemp, nTemp + current.sumPath);
pQueue.Enqueue(newNode, newNode.sumPath);
visited.Add(nTemp);
}
str[i] = temp;
}
}
//Increase
for (int i = str.Length - 1; i >= 0; i--)
{
if (str[i] != '9')
{
char temp = str[i];
str[i] = (char)((int)str[i] + 1);
int nTemp = Int32.Parse(str.ToString());
if (!visited.Contains(nTemp) && !IsPrimeMillerRabin(nTemp))
{
NumberAndSumPath newNode = new NumberAndSumPath(nTemp, nTemp + current.sumPath);
pQueue.Enqueue(newNode, newNode.sumPath);
visited.Add(nTemp);
}
str[i] = temp;
}
}
}
return -1;
}
public class NumberAndSumPath
{
public int number;
public int sumPath;
public NumberAndSumPath(int number, int sumPath)
{
this.number = number;
this.sumPath = sumPath;
}
}
public bool IsPrimeMillerRabin(BigInteger n)
{
if (millerRabinCache.Contains(n)) return true;
//It does not work well for smaller numbers, hence this check
int SMALL_NUMBER = 1000;
if (n <= SMALL_NUMBER)
{
bool val = IsPrime(n);
if (val) millerRabinCache.Add(n);
return val;
}
int MAX_WITNESS = 100;
for (long i = 2; i <= MAX_WITNESS; i++)
{
if (IsPrime(i) && Witness(i, n) == 1)
{
return false;
}
}
millerRabinCache.Add(n);
return true;
}
public BigInteger SqRtN(BigInteger N)
{
/*++
* Using Newton Raphson method we calculate the
* square root (N/g + g)/2
*/
BigInteger rootN = N;
int count = 0;
int bitLength = 1;
while (rootN / 2 != 0)
{
rootN /= 2;
bitLength++;
}
bitLength = (bitLength + 1) / 2;
rootN = N >> bitLength;
BigInteger lastRoot = BigInteger.Zero;
do
{
if (lastRoot > rootN)
{
if (count++ > 1000) // Work around for the bug where it gets into an infinite loop
{
return rootN;
}
}
lastRoot = rootN;
rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
}
while (!((rootN ^ lastRoot).ToString() == "0"));
return rootN;
}
public bool IsPrime(BigInteger n)
{
if (n <= 1)
{
return false;
}
if (n == 2)
{
return true;
}
if (n % 2 == 0)
{
return false;
}
for (int i = 3; i <= SqRtN(n) + 1; i += 2)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
private int Witness(long a, BigInteger n)
{
BigInteger t, u;
BigInteger prev, curr = 0;
BigInteger i;
BigInteger lln = n;
u = n / 2;
t = 1;
while (u % 2 == 0)
{
u /= 2;
t++;
}
prev = BigInteger.ModPow(a, u, n);
for (i = 1; i <= t; i++)
{
curr = BigInteger.ModPow(prev, 2, lln);
if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
prev = curr;
}
if (curr != 1) return 1;
return 0;
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private double priority;
public HeapEntry(object item, double priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public double Priority
{
get
{
return priority;
}
}
}
private bool ascend;
private int count;
private int capacity;
private HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue(bool ascend, int cap = -1)
{
capacity = 10000000;
if (cap > 0) capacity = cap;
heap = new HeapEntry[capacity];
this.ascend = ascend;
}
public object Dequeue(out double priority)
{
priority = heap[0].Priority;
object result = heap[0].Item;
count--;
trickleDown(0, heap[count]);
return result;
}
public object Peak(out double priority)
{
priority = heap[0].Priority;
object result = heap[0].Item;
return result;
}
public object Peak(/*out double priority*/)
{
//priority = heap[0].Priority;
object result = heap[0].Item;
return result;
}
public void Enqueue(object item, double priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}
private void bubbleUp(int index, HeapEntry he)
{
int parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
if (this.ascend)
{
while ((index > 0) && (heap[parent].Priority > he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
else
{
while ((index > 0) && (heap[parent].Priority < he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
}
public int SmallestNumber(int n, int t)
{
for (int k = n; ; k++)
{
long p = 1;
int temp = k;
while (temp > 0)
{
p *= (temp % 10);
temp /= 10;
}
if (p % t == 0) return k;
}
}
public int CountKConstraintSubstrings(string s, int k)
{
int retVal = 0;
for (int i = 0; i < s.Length; i++)
{
int zeroes = 0;
int ones = 0;
for (int j = i; j < s.Length; j++)
{
if (s[j] == '0') zeroes++;
else ones++;
if (zeroes > k && ones > k) break;
retVal++;
}
}
return retVal;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
if (this.ascend)
{
if (((child + 1) < count) &&
(heap[child].Priority > heap[child + 1].Priority))
{
child++;
}
}
else
{
if (((child + 1) < count) &&
(heap[child].Priority < heap[child + 1].Priority))
{
child++;
}
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
} 
Comments
Post a Comment