Missing Numbers in Consecutive List

[ganeshsrivatsa]

Hello All,

I am having 1000 consecutive numbers always starting with 1, and there could be upto 24 missing numbers from the list.
My question is, what pieces of information should I have in order to find out those missing numbers.

So far I came up with,

1. Sum of missing numbers.
2. Number of numbers missing from the list.

I know that the above information is not enough. let's say sum of missing numbers is 9 and numbers missing are two, it can be 3 and 6 or 5 and 4.
I can Have multiplication of missing numbers(?) but that might turn into a huge number.

Please help with this solution. I am building a computer program that finds out missing numbers with as less information as possible.

Thanks,

Ganesh.

 

[PeroK]

Can you explain the scenario and constraints you have here? The simplest way to communicate the missing numbers is to list them. What sort of solution are you looking for as an alternative to this?

 

[ganeshsrivatsa]

Hello PeroK.

The problem is I don't want to list them. I want to maintain as less information as possible as to compute the numbers.

What I am actually trying to do is. I am trying to capture hours of operation for a facility.

Each day of the week there can be up to two hours of operation like 10-12 and 2-5, that give 7*4 28 points per week. total number of minutes in a week is 10080. I am trying find a way to capture the 28 possible points in these minutes and build the hours of operation for that facility.

I could simply capture the points. But that is 28 pieces of information. Instead of that, I want a way to find these points by maintaining 3-4 pieces of information.

Coming to the actual scenario, I have 10080 consecutive numbers that start with 1, I want a way to compute up to 28 missing numbers by maintaining as less information as possible like sum, etc.

Please let me know if you need additional information.

Thanks,

Ganesh.

 

[PeroK]

It depends how you define information and why 3-4 pieces of information is better than 24. For example, you could communicate a single number where 0000, say, represents the end of one number and the next. So if the missing numbers were 5, 7 and 8, you would commincate the single piece of information:

50000700008

That's a single piece of information!

Or 5X7X8 would be even better.

 

[ganeshsrivatsa]

Hi PeroK,

Sorry for not giving you any detailed constraints. I am going to store this data into a database. So 28 columns makes the table horizontally large and very difficult for processing.

The solution you have for three numbers 50000700008 makes very large string for 28 numbers. means A string of at least 112 characters or numbers.

I am not very attracted to store direct data. Because the only way you could store it is by storing 28 pieces of information whether concatenated together or not. let's assume the following works.

I store the sum of numbers 15.
Number off numbers missing 5
Multiplication of numbers = 120.

Then based on the above data I will write a program that computes the missing numbers = 1,2,3,4,5.

That is how I want to store my data and compute the hours of operation based on the information available.

I wanted to know if there is any thing special about consecutive numbers and missing numbers within them in mathematics. I am not that good at Math.

Thanks,

Ganesh

 

[PeroK]

There's nothing wrong with having 28 columns in a table. If you have 28 pieces of data, you need 28 columns.

 

[ganeshsrivatsa]

Thanks for the suggestions.

Isnt there any way to find missing numbers from consecutive list from mathematics point of view?

Thanks,

G.

 

[jbriggs444]

Isnt there any way to find missing numbers from consecutive list from mathematics point of view?

As I understand the challenge, the point is not to "find" the missing numbers. It is to "encode" the missing numbers using a minimum of storage. That is to say it is an exercise in data compression.

Assume that all combinations of missing numbers have the same probability of occurrence. How many possible combinations are there?

The problem statement says that "up to 24" numbers can be missing from a list of 1000 total.

If there are no missing numbers then there is only one possibility. If there is one missing number then there are 1000 possibilities. If there are two missing numbers then there are 1000 * 999 / 2 possibilities. In general, if there are r missing numbers from a list of size n then there are ${{n}\choose{r}}$ possibilities. This is the number of "combinations of n things taken r at a time".

If you add up ${{1000}\choose{i}}$ for i ranging from zero to 24 then you get the total number of possible sets of missing numbers.

All you have to do is encode each possible combination as an integer in the range from 0 to this total minus one and store this in a [suitably sized] integer field in your database. Then eventually retrieve the integer and decode it. The encoding and decoding routines could be coded in a fairly straightforward fashion with a recursive function.

I do not recommend any such fancy stuff in a production application. Keep it simple. Don't force the guy who comes after you to try to understand your magic. My estimates put the size of the required integer field in the neighborhood of 161 bits.