CODEWITHSUNDEEP
javaarraysif-statementfor-loop
Gerret
Gerret

Reputation: 3046

Get the missing digits of an array

I have an array with digits and that array is not sorted. The user is able to delete numbers from the array. But the user should be able to add the digit later.

Basically I want to write in a database the id. The user is able to remove rows but if he add a row the id should be a missing digit from a deleted row.

At the moment I solve it like that:

for (Object[] object : data) {
    if ((int) object[1] > id) {
        id = (int) object[1];
    }
}

But with that I only get the largest number and not the missing number. How I am able to get a missing number?

Example:

4, 2, 3, 1 the user deletes row 2 and row 4 so I have

3, 1 now I want to calculate or with if statements whatever to get the 2 and, if the user add a another row the, 4 back.

Keep in mind that the user could close the program, so it is not possible to save the numbers in a other array!

Upvotes: 0

Views: 910

Answers (5)

nommyravian
nommyravian

Reputation: 1336

If you sort the id's in a temporary storage so it would be simple to find the first missing number;

int arr[] = {0,1,2,5}; //think you've the sorted array now
int missing = arr.length; //would have the last id+1 if there is no missing id
for (int i = 0; i < arr.length; i++) {
    if (i != arr[i]) {
         missing = i;
         break;
    }
}
System.out.println(missing); //3 will be printed.

Upvotes: 0

q99
q99

Reputation: 1011

From your example, sum the numbers from the beginning to the end, 1+2+3+4 = 10 and subtract the sum of the numbers you have, 1+2+4 = 7

So 10 - 7 = 3 (the missing number)

----------------------------------------------------EDIT ---------------- how about this?

public class SandBox7 {
public static void main(String[] args) {
    Integer[] array = new Integer[] { 1, 4, 9 };
    SandBox7 s = new SandBox7();
    List<Integer> mis = s.getMissingNumbers(array);
}

public List<Integer> getMissingNumbers(Integer[] in) {
    int max = getMaximum(in);
    // System.out.println(max);
    List<Integer> numbers = Arrays.asList(in);

    ArrayList<Integer> missing = new ArrayList<>();
    for (int i = 1; i < max; i++) {

        if (!numbers.contains(i)) {
            missing.add(i);
        }
    }
    return missing;
}

private int getMaximum(Integer[] in) {
    int tmp = -1;
    for (int i = 0; i < in.length; i++) {
        if (tmp < in[i])
            tmp = in[i];
    }
    return tmp;
}

}

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109547

You have some possibilities, and it is a design problem you have to decide yourself. Just some alternatives:

  1. Best: renumber IDs on deletion, but needs meta information on referencing foreign keys.

  2. If the data is ordered by ID. The numbers of deletions when not renumbered:

    int deletions = data.length
                - (data.length == 0 ? 0 : data[data.length - 1][1]);

    With a binary search, you can find a deleted hole (shifted number).

  3. Unordered. Keep the number of deletions maybe. Keep an unbounded BitSet of data.length bits.

    Or alternatively a Set<Integer> with deletions. And renumber when the set becomes too large. (A set of ranges from-ID upto to-ID would be better.)

Upvotes: 0

Vimal Bera
Vimal Bera

Reputation: 10497

Look at below code..might be helpful

    int data[]={1,2,4};
    int i=1;
    for(Object object : data){
        if((Integer)object!=i++)
            break;
    }
    System.out.println(i-1);//This will print 3.

Upvotes: 1

Subhrajyoti Majumder
Subhrajyoti Majumder

Reputation: 41200

One approach could be maintaining a parallel array which will contain the deleted number. 

Object[] data = ...;
Object[] delData = ...;

So every time you insert/add a new number you need to check that number exists in parallel array or not.

Upvotes: 0

Related Questions