CODEWITHSUNDEEP
javaarraysalgorithm
Artemkller545
Artemkller545

Reputation: 999

Find what number it used to be before element reset

Given an array with any size, in my case the array size is 5.

This array contains ALL numbers from 1 to 5 (must contain all of them)

[1 | 2 | 3 | 4 | 5]
 0   1   2   3   4

And now, one element was reset and was set to 0, and the mission is to find what number it used to be before it turned 0.

So I have this simple solution:

Explained: First, loop from 1 to 5, create an inner loop to check if the i from the first loop exists in the whole array, if it doesn't exist, that means that it is the value it used to be before 0, because the array contained all numbers from 1 to 5 or 1 to 100 (doesn't matter) and there's on'y one rested element.

Code:

    int[] numbers = new int[]{1, 2, 3, 4, 5};
    numbers[1] = 0;

    int lost = -1;

    loop: 
    for (int i = 1; i <= numbers.length; i++) {
        for (int j = 0; j < numbers.length; j++) {
            if (numbers[j] == i) {
                continue loop;
            }
        }
        lost = i;
        break loop;
    }

    System.out.println(lost);

That solution is not bad, but I think there's a better solution, something more stable.

I have thought about it mathematically, in our example:

1 + x + 3 + 4 + 5 = 15
x = 2

Mathematically, it's really easy. Is there a way this can be done in a programming language as easy as it is mathematically? Any better algorithms you can think of to solve this question?

Upvotes: 0

Views: 63

Answers (2)

XOR-Manik
XOR-Manik

Reputation: 503

There is one more possibility, you can use HashMaps! you don't have to traverse through any "for loops" then.

You can use Hashmaps to check whether is there any value for the key of "0", if yes then that is the case where some number is reset to 0. Then you can traverse the Hashmap and compare which value is missing.

Everything is done With O(1) complexity and worst case of O(n) complexity.

Upvotes: 0

Shar1er80
Shar1er80

Reputation: 9041

This works for ONE element being reset. Just subtract each remaining element from the sum and what ever is left over would have been the previous number the element was before it was reset.

public static void main(String[] args) throws Exception {
    int sum = 15;
    int[] numbers = new int[] { 1, 2, 3, 4, 5 };

    numbers[4] = 0;
    for (int i = 0; i < numbers.length; i++) {
        sum -= numbers[i];
    }
    System.out.println(sum);
}

Results:

5

Upvotes: 2

Related Questions