[JAVA] [100%] PermMissingElem (src & jUnit)

Painless

PermMissingElem

Find the missing element in the specified permutation. image.png

Task description

Given an array A consisting of N different integers. The array contains integers in the range [1 .. (N + 1)]. This means that one element is missing.

Your goal is to find that missing element.

Write a function:

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

Given array A, returns the value of the missing element.

For example, given the following array A:

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

The function must return 4 because it is a missing element.

Write an efficient algorithm for the following assumptions:


solve

Program [Proposal 1: Arrays.sort]

PermMissingElemSolutionSort.java

PermMissingElemSolutionSort.java


    public int solution(int[] A) {
        if (A.length == 0) return 1;

        java.util.Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {
            if ((i + 1) != A[i]) return i + 1;
        }
        return A.length + 1;
    }

Detected time complexity:
O(N) or O(N * log(N))

jUnit PermMissingElemSolutionSortTest.java


Program [Proposal 2: data bucket]

PermMissingElemSolutionBucket.java

PermMissingElemSolutionBucket.java


    public int solution(int[] A) {
        boolean[] bucket = new boolean[100000 + 2];
        java.util.Arrays.fill(bucket, false);
        for (int anA : A) {
            bucket[anA] = true;
        }
        for (int i = 1; i < bucket.length; i++) {
            if (!bucket[i]) {
                return i;
            }
        }

        return 1;
    }

Detected time complexity:
O(N) or O(N * log(N))

jUnit PermMissingElemSolutionBucketTest.java


Recommended Posts

[100%] PermMissingElem (src & jUnit)
[100%] CyclicRotation (src & jUnit)
[100%] FrogJmp (src & jUnit)
[100%] FrogRiverOne (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] MinAvgTwoSlice (src & junit)
[100%] PassingCars (src & junit)
[100%] PermCheck (src & junit)
[100%] TapeEquilibrium (src & jUnit)
[100%] MaxProductOfThree (src & jUnit)
[100%] BinaryGap (src & jUnit)
[100%] MissingInteger (src & junit & author's note)
[100%] [GenomicRangeQuery] (src & junit & author's note)
[100%] MaxCounters (src & junit & author's note)
[100%] Distinct (src & junit & author's note)
[100%] CountDiv (src & junit & author's note)
junit
JUnit 4 notes
JUnit story
JUnit memorandum