Find the element that appears twice in an array where every other element appears once

  • Boolean[] uses about 4-20 bytes per boolean value.

  • boolean[] uses about 1 byte per boolean value.

  • BitSet uses about 1 bit per boolean value.

Memory size might not be an issue for you in which case boolean[] might be simpler to code.

package com.company;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
public class Algorithm {
    List<Integer> duplicate(int[] arr, int maxSize) {
        if (arr.length == 0) {
            throw new RuntimeException("Invalid length");
        }
        List<Integer> duplicate = new ArrayList<>();
        BitSet b = new BitSet(maxSize + 1);
        b.set(0, maxSize, false);
        for (int item : arr) {
            if (!b.get(item)) {
                b.set(item, true);
            } else {
                duplicate.add(item);
            }
        }
        return duplicate;
    }
}
package com.company;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.List;
public class AlgorithmTest {
    @Test
    void largestAndSmallest1() {
        Algorithm algorithm = new Algorithm();
        int[] array = new int[]{2, 4, 6, 0, 6, 4, 2};
        List<Integer> duplicate = algorithm.duplicate(array, 6);
        Assertions.assertEquals(Arrays.asList(6, 4, 2), duplicate);
    }
    @Test
    void largestAndSmallest2() {
        Algorithm algorithm = new Algorithm();
        int[] array = new int[]{10, 3, 5, 5, 1, 10};
        List<Integer> duplicate = algorithm.duplicate(array, 10);
        Assertions.assertEquals(Arrays.asList(5, 10), duplicate);
    }
}
plugins {
    id 'java'
}

group 'org.example'
version '1.0-SNAPSHOT'

repositories {
    mavenCentral()
}

dependencies {
    testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}

test {
    useJUnitPlatform()
}

 

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Algorithm {
    List<Integer> duplicate(int[] arr, int maxSize) {
        if (arr.length == 0) {
            throw new RuntimeException("Invalid length");
        }
        List<Integer> duplicate = new ArrayList<>();
        boolean[] b = new boolean[maxSize + 1];
        for (int item : arr) {
            if (!b[item]) {
                b[item] = true;
            } else {
                duplicate.add(item);
            }
        }
        return duplicate;
    }
}
package com.company;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.List;

public class AlgorithmTest {
    @Test
    void largestAndSmallest1() {
        Algorithm algorithm = new Algorithm();
        int[] array = new int[]{2, 4, 6, 0, 6, 4, 2};
        List<Integer> duplicate = algorithm.duplicate(array, 6);
        Assertions.assertEquals(Arrays.asList(6, 4, 2), duplicate);
    }

    @Test
    void largestAndSmallest2() {
        Algorithm algorithm = new Algorithm();
        int[] array = new int[]{10, 3, 5, 5, 1, 10};
        List<Integer> duplicate = algorithm.duplicate(array, 10);
        Assertions.assertEquals(Arrays.asList(5, 10), duplicate);
    }
}
plugins {
    id 'java'
}

group 'org.example'
version '1.0-SNAPSHOT'

repositories {
    mavenCentral()
}

dependencies {
    testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}

test {
    useJUnitPlatform()
}

 

follow us on