On the Collatz Conjecture II
I've written about the Collatz Conjecture before, right here: https://anothercasualcoder.blogspot.com/2019/05/on-collatz-conjecture.html
Coincidentally, this LC problem talks about it. Here it is: https://leetcode.com/problems/sort-integers-by-the-power-value/
As I mentioned in the previous Collatz Conjecture post, this is one of the open problems in math which can pay up to 1ドルM for a mathematical solution that (dis)proves that every positive integer N will eventually be transformed to 1 by following the operations listed by Collatz.
The problem in this post can be solved by:
A) Create a function to calculate the Collatz length of a number. Use memoization to speed things up
B) Push the values to a PQueue - careful with the priority, you need to take into account when Collatz(X) = Collatz(Y) but X != Y
C) Dequeue until Kth value
Code is below, cheers, stay safe from COVID19!!! ACC.
public class Solution
{
public int GetKth(int lo, int hi, int k)
{
int[] arr = new int[hi - lo + 1];
Hashtable cache = new Hashtable();
for (int index = 0, i = lo; i <= hi; i++, index++)
arr[index] = Collatz(i, cache);
PriorityQueue pQueue = new PriorityQueue();
for (int index = 0, i = lo; i <= hi; i++, index++)
pQueue.Enqueue(i, arr[index] * (hi + 1) + i);
int retVal = 0;
while (k-- > 0)
retVal = (int)pQueue.Dequeue();
return retVal;
}
private int Collatz(int n, Hashtable cache)
{
if (cache.ContainsKey(n)) return (int)cache[n];
int collatz = (n > 1) ? (1 + Collatz(n % 2 == 0 ? n / 2 : 3 * n + 1, cache)) : 0;
if (!cache.ContainsKey(n)) cache.Add(n, collatz);
return collatz;
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private int priority;
public HeapEntry(object item, int priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public int Priority
{
get
{
return priority;
}
}
}
private int count;
private int capacity;
public HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue()
{
capacity = 1000000;
heap = new HeapEntry[capacity];
}
public object Dequeue()
{
object result = heap[0].Item;
//priority = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, int 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
while ((index > 0) && (heap[parent].Priority > he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
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);
}
}
Coincidentally, this LC problem talks about it. Here it is: https://leetcode.com/problems/sort-integers-by-the-power-value/
1387. Sort Integers by The Power Value
Medium
The power of an integer
x is defined as the number of steps needed to transform x into 1 using the following steps:- if
xis even thenx = x / 2 - if
xis odd thenx = 3 * x + 1
For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).
Given three integers
lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.
Return the
k-th integer in the range [lo, hi] sorted by the power value.
Notice that for any integer
x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.
Example 1:
Input: lo = 12, hi = 15, k = 2 Output: 13 Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1) The power of 13 is 9 The power of 14 is 17 The power of 15 is 17 The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13. Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.
Example 2:
Input: lo = 1, hi = 1, k = 1 Output: 1
Example 3:
Input: lo = 7, hi = 11, k = 4 Output: 7 Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14]. The interval sorted by power is [8, 10, 11, 7, 9]. The fourth number in the sorted array is 7.
Example 4:
Input: lo = 10, hi = 20, k = 5 Output: 13
Example 5:
Input: lo = 1, hi = 1000, k = 777 Output: 570
Constraints:
1 <= lo <= hi <= 10001 <= k <= hi - lo + 1
As I mentioned in the previous Collatz Conjecture post, this is one of the open problems in math which can pay up to 1ドルM for a mathematical solution that (dis)proves that every positive integer N will eventually be transformed to 1 by following the operations listed by Collatz.
The problem in this post can be solved by:
A) Create a function to calculate the Collatz length of a number. Use memoization to speed things up
B) Push the values to a PQueue - careful with the priority, you need to take into account when Collatz(X) = Collatz(Y) but X != Y
C) Dequeue until Kth value
Code is below, cheers, stay safe from COVID19!!! ACC.
public class Solution
{
public int GetKth(int lo, int hi, int k)
{
int[] arr = new int[hi - lo + 1];
Hashtable cache = new Hashtable();
for (int index = 0, i = lo; i <= hi; i++, index++)
arr[index] = Collatz(i, cache);
PriorityQueue pQueue = new PriorityQueue();
for (int index = 0, i = lo; i <= hi; i++, index++)
pQueue.Enqueue(i, arr[index] * (hi + 1) + i);
int retVal = 0;
while (k-- > 0)
retVal = (int)pQueue.Dequeue();
return retVal;
}
private int Collatz(int n, Hashtable cache)
{
if (cache.ContainsKey(n)) return (int)cache[n];
int collatz = (n > 1) ? (1 + Collatz(n % 2 == 0 ? n / 2 : 3 * n + 1, cache)) : 0;
if (!cache.ContainsKey(n)) cache.Add(n, collatz);
return collatz;
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private int priority;
public HeapEntry(object item, int priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public int Priority
{
get
{
return priority;
}
}
}
private int count;
private int capacity;
public HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue()
{
capacity = 1000000;
heap = new HeapEntry[capacity];
}
public object Dequeue()
{
object result = heap[0].Item;
//priority = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, int 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
while ((index > 0) && (heap[parent].Priority > he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
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
[フレーム]