Struggling with Integers (Maximum Integer Size)

struggling with integers (maximum integer size)

The largest integer R can hold is

.Machine$integer.max
# [1] 2147483647

This has nothing to do with scientific notation and everything to do with how the computer actually stores the numbers. The current version of R stores integers still as 32bit, regardless of the architecture. This might change in the future though.

see also ?as.integer

Currently you can get access to 64 bit integers through the int64 package

> as.integer(.Machine$integer.max)
[1] 2147483647
> # We get problems with this
> as.integer(.Machine$integer.max + 1)
[1] NA
Warning message:
NAs introduced by coercion 
> # But if we use int64
> library(int64)
> as.int64(.Machine$integer.max) + 1L
[1] 2147483648

Get min and max integer value containing X number of digits

Fox any x>1, the min value would be 10^x-1. E.g.:

• If x = 2, min=10^2-1 = 10¹ = 10
• If x = 3, min=10^3-1 = 10² = 100
• If x = 4, min=10^4-1 = 10³ = 1000

For x=1, since it's the only value that is not a one followed by a series of zeroes, you'll need special treatment.

public static int MinIntWithXDigits(this int x)
{
    if (x == 0) 
    {
        throw new ArgumentException(nameof(x), "An integer cannot contain zero digits.");
    }

    if (x == 1) {
        return 0;
    }

    try
    {
        return Convert.ToInt32(Math.Pow(10, x - 1));
    }
    catch 
    {
        throw new InvalidOperationException($"A number with {x} digits cannot be represented as an integer.");
    }
}

Side note:

If the result were restricted to positive integers instead of non-negative integers, the smallest integer with one digit would be 1, and the general formula would have applied for this case too.

Matching integers to ranges

Here's an idea: When an interval ends, you can't put an integer greater than the end in that interval. This means that you need to satisfy the ranges that end sooner first, if you intend to fill as many as possible. Now, what do you do when two intervals have equal ends? You fill the one that starts sooner. This way you increase your chances of filling the next range/interval with the same ending but a late start.

Now, suppose we sort the integers none-decreasing and the intervals, first by end then start, none-decreasing and start to fill the intervals greedily. What could happen is that an interval lands at the end of the intervals array, since it has a large end, while it has a very small start. When we go over our integers, if we skipped an integer because the first interval's start is greater than that integers, we run the risk to ignore it while we could have fitted the integer in that later coming interval with the large end and very small start.

To mitigate that, we need to check all the remaining intervals for every integer that we consider, and take the first one where we can fit the integer, if any. This deteriorates our run time complexity into an O(n * m), but I don't see how we could overcome that to make it linearithmic.

Here's the above idea converted into an algorithm:

1. Sort your ranges/intervals by end then start none-decreasing.
2. Sort your integers none-decreasing.
3. Have a set where you keep track of the used intervals, used_intervals.
4. Have an array for the resulting integers, res.
5. Run the following nested loop:

for integer in integers:
  for interval in intervals:
    if interval in used_intervals: continue
    if interval.start <= integer <= interval.end:
      res.push(integer)
      used_intervals.add(interval)

Time complexity analysis:

• Sorting the intervals is O(m * log m) where m is the number of intervals
• Sorting the integers is O(n * log n) where n is the number of integers
• The nested loop is O(m * n)
  Since n <= m, this reduces the time complexity in terms of Big O to O(max(m * n, m * log m)).

Space complexity analysis:
O(m), sorting, the result array, the set

I'm not sure if we can optimize this, not the time complexity but still an optimization. Any feedback is appreciated.

---

Related Topics