steelmonkey steelmonkey -4 years ago 55
Java Question

What is the right way to solve Codility's PermMissingElem test? (Java)

I have the following problem taken from Codility's code testing exercises:

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

the function should return 4, as it is the missing element.

Assume that:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].


expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not >counting the storage required for input arguments).

Elements of input arrays can be modified.

My approach was to convert the given array into an ArrayList, use the ArrayList to find the lowest and highest values inside the array, and iterate through all possible values from lowest to highest, and then return the missing value.

This solves the example problem, but my problem seems to be that I cannot get right answers under the following conditions of the given array:

"empty list and single element"

"the first or the last element is missing"

"single element"

"two elements"

What am I doing wrong, and what is the proper way to go about solving this problem?

Answer Source

This problem has a mathematical solution, based on the fact that the sum of consecutive integers from 1 to n is equal to n(n+1)/2.

Using this formula we can calculate the sum from 1 to N+1. Then with O(N) time complexity we calculate the actual sum of all elements in the array.

The difference between the full and actual totals will yield the value of the missing element.

Space complexity is O(1).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download