PermMissingelem
Problem specification
Task descriptionA 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:
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).
Codes explained:
if array's size = 0, return 1.
if A[i+1] inside a sorted array, when subtracted from A[i], result in 2, return A[i+1]+A[i])/2; (ex. (6+4)/2 = 5)
if answer's still not found, it's either the first index or the last index that' missing.
if array's size = 0, return 1.
if A[i+1] inside a sorted array, when subtracted from A[i], result in 2, return A[i+1]+A[i])/2; (ex. (6+4)/2 = 5)
if answer's still not found, it's either the first index or the last index that' missing.
Answer
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes,
e.g. // System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length == 0)
return 1; Arrays.sort(A);
for(int i = 0; i < A.length-1; i++)
{
if(A[i+1]-A[i] == 2)
return (A[i+1]+A[i])/2; }
if(A[0] == 1)
return A[A.length-1]+1;
else return 1;
}
}
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes,
e.g. // System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length == 0)
return 1; Arrays.sort(A);
for(int i = 0; i < A.length-1; i++)
{
if(A[i+1]-A[i] == 2)
return (A[i+1]+A[i])/2; }
if(A[0] == 1)
return A[A.length-1]+1;
else return 1;
}
}