codility absolute distinct count from an array

Question

so i took the codility interview test yesterday and was informed today that i failed, unfortunately i wasnt given any other information by either codility nor the employer as to where i screwed up so i would appreciate some help in knowing where i went wrong. i know codility pays alot of emphasis on how fast the program runs and how it behaves for large numbers. now i didnt copy paste the questions so this the approx of what i remember

1. count the number of elements in an array a which are absolute distinct, what it means is if an array had -3 and 3 in it these numbers are not distinct because|-3|=|3|. i think an example would clear it up better

a={-5,-3,0,1,-3} the result would be 4 because there are 4 absolute distinct elements in this array.

The question also stated that a.length would be <=10000, and most importantly it stated that assume that the array is sorted in ascending order but i didnt really understand why we would need it to be sorted

IF YOU THINK I MISSED SOMETHING ASK AND I WILL TRY TO CLEAR UP THE QUESTION FURTHER.

here is my code

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;


public class test2 {

    int test(int[] a){
        Set<Integer> s=new HashSet<Integer>();

        for(int i=0;i<a.length;i++){
            s.add(Math.abs(a[i]));

        }
        return s.size();

    }

    public static void main(String[] args) {
        test2 t=new test2();
        int[] a={1,1,1,2,-1};
        System.out.println(t.test(a));

    }

}

Answer 1

If the array is sorted you can find duplicates by looking a neighbours. To compare absolute values to need to start at both the start and the end. This avoid creating a new structure.

EDIT: IMHO HashMap/HashSet is O(log(log(n)) due to collisions, it is only O(1) if there is a perfect hash function. I would have thought not creating object which be much much faster but appears to be only 4x fast on my machine.

In summary, you can see that using a Set is simpler, clearer and easier to maintain. It is still very fast and would be the best solution in 98% of cases.

public static void main(String[] args) throws Exception {
    for (int len : new int[]{100 * 1000 * 1000, 10 * 1000 * 1000, 1000 * 1000, 100 * 1000, 10 * 1000, 1000}) {
        int[] nums = new int[len];
        for (int i = 0; i < len; i++)
            nums[i] = (int) (Math.random() * (Math.random() * 2001 - 1000));
        Arrays.sort(nums);

        long timeArray = 0;
        long timeSet = 0;
        int runs = len > 1000 * 1000 ? 10 : len >= 100 * 1000 ? 100 : 1000;
        for (int i = 0; i < runs; i++) {
            long time1 = System.nanoTime();
            int count = countDistinct(nums);
            long time2 = System.nanoTime();
            int count2 = countDistinctUsingSet(nums);
            long time3 = System.nanoTime();
            timeArray += time2 - time1;
            timeSet += time3 - time2;
            assert count == count2;
        }
        System.out.printf("For %,d numbers, using an array took %,d us on average, using a Set took %,d us on average, ratio=%.1f%n",
                len, timeArray / 1000 / runs, timeSet / 1000 / runs, 1.0 * timeSet / timeArray);
    }
}

private static int countDistinct(int[] nums) {
    int lastLeft = Math.abs(nums[0]);
    int lastRight = Math.abs(nums[nums.length - 1]);
    int count = 0;
    for (int a = 1, b = nums.length - 2; a <= b;) {
        int left = Math.abs(nums[a]);
        int right = Math.abs(nums[b]);
        if (left == lastLeft) {
            a++;
            lastLeft = left;
        } else if (right == lastRight) {
            b--;
            lastRight = right;
        } else if (lastLeft == lastRight) {
            a++;
            b--;
            lastLeft = left;
            lastRight = right;
            count++;
        } else if (lastLeft > lastRight) {
            count++;
            a++;
            lastLeft = left;
        } else {
            count++;
            b--;
            lastRight = right;
        }
    }
    count += (lastLeft == lastRight ? 1 : 2);
    return count;
}

private static int countDistinctUsingSet(int[] nums) {
    Set<Integer> s = new HashSet<Integer>();
    for (int n : nums)
        s.add(Math.abs(n));
    int count = s.size();
    return count;
}

prints

For 100,000,000 numbers, using an array took 279,623 us on average, using a Set took 1,270,029 us on average, ratio=4.5

For 10,000,000 numbers, using an array took 28,525 us on average, using a Set took 126,591 us on average, ratio=4.4

For 1,000,000 numbers, using an array took 2,846 us on average, using a Set took 12,131 us on average, ratio=4.3

For 100,000 numbers, using an array took 297 us on average, using a Set took 1,239 us on average, ratio=4.2

For 10,000 numbers, using an array took 42 us on average, using a Set took 156 us on average, ratio=3.7

For 1,000 numbers, using an array took 8 us on average, using a Set took 30 us on average, ratio=3.6

---

On @Kevin K's point, even Integer can have collision even through it's hash values are unique, it can map to the same bucket as the capacity is limited.

public static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public static void main(String[] args) throws Exception {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(32, 2.0f);
    for (int i = 0; i < 10000 && map.size() < 32 * 2; i++) {
        if (hash(i) % 32 == 0)
            map.put(i, i);
    }
    System.out.println(map.keySet());
}

prints

[2032, 2002, 1972, 1942, 1913, 1883, 1853, 1823, 1763, 1729, 1703, 1669, 1642, 1608, 1582, 1548, 1524, 1494, 1456, 1426, 1405, 1375, 1337, 1307, 1255, 1221, 1187, 1153, 1134, 1100, 1066, 1032, 1016, 986, 956, 926, 881, 851, 821, 791, 747, 713, 687, 653, 610, 576, 550, 516, 508, 478, 440, 410, 373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]

The values are in reverse order because the HashMap has generated into a LinkedList.

Answer 2

You should have pay attention to the fact that the array is sorted in ascending order.

Lets assume that there are only positive numbers, or the question was not about absolute distinct.

The you could count the Number by iterating trough the list, and increment the counter by one, if the actual element is different from the last. (and +1 for the first element)

If you understand that, you can add the absolute distinct constraint. For example by improving the algorithm by two pointers, one starting from the begin, one from the end. Then you have also to take care that both pointers works like in parallel, so that both pointers will end at 0 or the absoulte lowest number (positive/negative) - This will complicate the whole stuff a bit, but it is possible.

Answer 3

int count(vector<int> &A) {

    int len = B.size();
    if (len <= 0)
        return 0;

    // make a copy and calc absolutes of all items
    vector<int> B = vector<int>(A);
    for (int i = 0; i < len; i++) {
        if (B[i] < 0) 
        B[i] = -B[i];
    }

    // and sort so we have a simple absolute count
    sort(B.begin(), B.end());

    int result = 1; //count first number always
    for (int j = 1; j < len; j++) {
        if (B[j] != B[j-1])
            result++;
    }
    return result;

}

Answer 4

this is what i came up with, not sure if the fact that it contains a for loop inside the while deems it as typical noobie mistake.

    private int getDistict(int[] myaa) {
        int dupcount=0;
        int i = 0;
        int j = myaa.length - 1;
        while (i < j) {
    //      check neighbors 
            if(Math.abs(myaa[i]) == Math.abs(myaa[i+1])) {
                dupcount++;
                i++;
                continue;
            }
//      check the other side
            if(myaa[i] < 0) {
                for(int k = j; Math.abs(myaa[i]) <= Math.abs(myaa[k]); k-- ) {
                    if(Math.abs(myaa[i])==Math.abs(myaa[k])){
                        dupcount++;
                    }
                }               
            }
            i++;
        }
        return myaa.length - dupcount;
    }

Answer 5

Here is a simple solution for this.

public class test{

public static int dis(Integer[] arr) {
    out.println(Arrays.asList(arr));
    if (arr.length == 0) {
        return 0;
    }
    int i = 0;
    int j = arr.length - 1;
    int c = 0;
    while (i <= j) {
        if ((j != arr.length - 1) && (Math.abs(arr[j]) == Math.abs(arr[j + 1]))) {
            out.println("skipping J==" + j);
            j--; continue;
        }
        if ((i != 0) && (Math.abs(arr[i]) == Math.abs(arr[i - 1]))) {
            out.println("skipping I==" + i);
            i++; continue;
        }
        if (Math.abs(arr[i]) < Math.abs(arr[j])) {
            j--;
            c++;
        }
        else if (Math.abs(arr[i]) > Math.abs(arr[j])) {
            i++; c++;
        }
        else {
            i++; j--; c++;
        }

        out.println("I=" + i + " J=" + j + " C=" + c);
    }
    return c;
}




public static void main(String[] arg){

//Integer[] a = {34,2,3,4,3,-2,3};
//out.println("distinct elements are" + dis(a));
Integer[] aa={-5,-3,0,1,3};
out.println("distinct elements count " + dis(aa));
Integer[] ab={-5,-3,0,1,3, 4, 6, 7};
out.println("distinct elements count " + dis(ab));
Integer[] ac={-5};
out.println("distinct elements count " + dis(ac));
Integer[] acc={9};
out.println("distinct elements count " + dis(acc));
Integer[] ad={9,9,9};
out.println("distinct elements count " + dis(ad));
Integer[] ae={-5,-5};
out.println("distinct elements count " + dis(ae));
Integer[] aee={1,5,5,5,5};
out.println("distinct elements count " + dis(aee));
Integer[] af={-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8};
out.println("distinct elements count " + dis(af));

}

}

out put is

[-5, -3, 0, 1, 3]
distinct elements count 4
[-5, -3, 0, 1, 3, 4, 6, 7]
distinct elements count 7
[-5]
distinct elements count 1
[9]
distinct elements count 1
[9, 9, 9]
distinct elements count 1
[-5, -5]
distinct elements count 1
[1, 5, 5, 5, 5]
distinct elements count 2
[-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8]
distinct elements count 8

Answer 6

Heres what I coded.....Let me know if it can be improved....

import java.util.Arrays;
import java.util.HashSet;

/********
Joel 
Jun 19, 2013
 ********/

public class CodilityTest {

    private int[] inputArray;
    public static int count=0;

    public void setInput(int [] givenIP){
        this.inputArray= new int[givenIP.length];
        for(int i=0; i<givenIP.length;i++)
        { inputArray[i] = givenIP[i];}
    }

    public int[] getInput(){
        return this.inputArray;
    }

    public CodilityTest(){
        count=0;
    }

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub

        CodilityTest o_tc = new CodilityTest();

        int [] x = {1,2,-3,4,-5,-11,-2,3,-4,5};
        int [] y = new int[0];
        o_tc.setInput(x);
        o_tc.getOutput(x);
        System.out.println(count);

        CodilityTest o_tc1 = new CodilityTest();
        o_tc1.getOutput(y);     
    }

    public void getOutput(int [] givenInput)
    {
        if(givenInput == null)
        {System.out.println("Please Enter some variables Sir."); return;}

        if(givenInput.length<1)
        {System.out.println("Please Enter some variables Sir."); return; }

        if(givenInput.length < 2)
        {count+=1; return;}

        HashSet<Integer> o_hs = new HashSet<Integer>();
        for(int numCount=0; numCount<givenInput.length;numCount++)
        {           
            if(o_hs.add(Math.abs(givenInput[numCount])))
            {count+=1;}
        }

    }

}

Answer 7

Since there's also the Python tag in the question asked, below is my simple solution in Python which might be useful to future users, and which gets 100% score, correctness, and performance on Codility:

def solution(N):

  list_of_absolute_values = list(map(lambda x:abs(x), N))

  return len(set(list_of_absolute_values))

In the 1st line of the function, map() converts all values to their absolute ones. We then return the number of distinct absolute values via the set() function which removes duplicates.

Answer 8

This is my version. What do you think?

int count(vector<int> testVector){

  for(unsigned int i = 0; i < testVector.size(); i++){
    // empty array, return 0
    if(testVector.empty()) return 0;

    // one number left, must be unique, return 1;
    if(testVector.size() == 1) return 1;

    // neighbour elements are the same, delete first element
    if(testVector[0] == testVector[1]) {
        testVector.erase(testVector.begin());
        return count(testVector);
    }

    // absolute value of first and last element identical, delete first element
    if(abs(testVector[0]) == abs(testVector[testVector.size() - 1])){
        testVector.erase(testVector.begin());
        return count(testVector);
    }

    // if absolute value of beginning is greater than absolute value of end, delete beginning, otherwise end
    if(abs(testVector[0]) > abs(testVector[testVector.size() - 1])){
        testVector.erase(testVector.begin());
    } else {
        testVector.erase(testVector.end() - 1);
    }       
    // increase counter and recurse
    return 1 + count(testVector);
  }
}

Answer 9

class Program
{
    static int CountArray(int[] MyIntArray)
    {
        int countNum = 0;
        int[] TempIntArray = new int[MyIntArray.Length];
        for (int i = 0; i < MyIntArray.Length; i++)
        {
            TempIntArray[i] = Math.Abs(MyIntArray[i]);
        }
        var queryResults = from n in TempIntArray 
                           select n;
        countNum = queryResults.Distinct().ToArray().Length;
        return countNum;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("demoX6FVFB-KX8");
        Random randomNumber = new Random();
        int[] TheArray = new int[100];
        for (int j = 0; j < TheArray.Length; j++)
        {
            TheArray[j] = randomNumber.Next(-50, 50);
        }
        int counta = Program.CountArray(TheArray);
        Console.WriteLine(counta);
    }
}

Answer 10

import java.util.Arrays;

public class DistinctNumbers {

    public static void main(String[] args) {

       int[][] tests = new int[][] {
                                 {-5,-3, 0, 1, 3},    //4
                                 {-5,-5,-5,-5,-5},   // 1
                                 { 1, 2, 3, 4, 5},   // 5
                                 { 1},               // 1
                                 { 1, 2},            // 2
                                 { 1, 1},            // 1
                        };

       for (int[] test : tests) {
           int count = findDistinctNumberCount( test );
           System.out.println(count);
       }

    }

    static int findDistinctNumberCount(int[] numbers) {

        // 1. make everything abs.
        for (int i=0; i<numbers.length; i++) {
          if (numbers[i] <0) {
              numbers[i] = Math.abs(numbers[i]);
          }
        }

        // 2. sort them
        Arrays.sort(numbers);

        // 3. find
        int count = numbers.length;

        for (int i=0; i<numbers.length; i++) {

            // skip if not distinct (equal)
            i = skipIfNeededAndGentNextIndex(i, numbers);

        }

        return count;

    }

    public static int skipIfNeededAndGentNextIndex(int currentIndex, int[] numbers) {

        int count = numbers.length;

        int nextIndex = currentIndex;

        if ( (nextIndex + 1) != numbers.length)  {

            nextIndex += 1;

            while(numbers[currentIndex] == numbers[nextIndex]) {

                count -= 1;

                if ( (nextIndex + 1) != numbers.length) {
                    nextIndex += 1;
                } else {
                    break;
                }

            }

        }

        return count;
    }

}

Answer 11

.NET C#:

static int absoluteDistinctNumbers(int[] arr)
{
    int same = 0;
    int l = 0;
    int r = arr.Length - 1;

    while (l < r)
    {
        if (Math.Abs(arr[l]) == Math.Abs(arr[r]))
            ++same;

        if (Math.Abs(arr[l]) > Math.Abs(arr[r]))
            ++l;
        else
            --r;
    }

    return arr.Length - same; 
}

Is there a problem with this solution? It looks much simpler than the other ones presented...and it took me like 10 minutes, so I am quite sure I did something wrong, but I have no idea what... My tests:

var arr = new int[] { 4, 2, 1, 1, -1, -5 };
var result = absoluteDistinctNumbers(arr);
Debug.Assert(4 == result);

arr = new int[] { 1, -1 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { };
result = absoluteDistinctNumbers(arr);
Debug.Assert(0 == result);

arr = new int[] { 2 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { 3, 3, -3 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { 2, 0, 0, 0 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(2 == result);

Answer 12

The shortest version here for time complexity O(n) and O(1) memory:

int countAbsDistinct(int[] A) {
    int start = 0;
    int end = A.length - 1;
    if (end == -1) { // zero size list
        return 0;
    }

    int c = 1; // at least one abs distinct for non-empty array
    while(A[start]<A[end]){
        int l = Math.abs(A[start]);
        int r = Math.abs(A[end]);
    c++;

        if (r>=l){
            while(A[end]==list.get(--end)); // move left until different value
        }
        if (l>=r){
            while(A[start]==list.get(++start)); // move right until different value
        }
    }
    if(start>end){ // if last movements made start index bigger than end
        c--;
    }
    return c;
}

Answer 13

In the case of Java, Arrays.sort() method has the best average performance. The expectation of time complexity is said to be O(N*log2N). So why not use it?

Here is a solution.

1. Go through the array, turn all the negative numbers into their absolute numbers. For example, from {-5, -3, 0, 1, 3} to {5, 3, 0, 1, 3}.
2. User Arrays.sort() to resort the array. For example, from {5, 3, 0, 1, 3} to {0, 1, 3, 3, 5}.
3. Go through the array again, if the neighbors do not have the same value, count up.

Here is the source in Java.

int countDistinct(int[] A) {

    int size = A.length;
    if(size == 0) {
        return 0;
    }
    for(int i = 0; i < size; i++) {
        if(A[i] < 0) {
            A[i] = (-1) * A[i];
        }
    }

    Arrays.sort(A);

    int count = 1;
    for(int i = 0; i < size - 1; i++) {
        if(A[i] != A[i + 1]) {
            count++;
        } 
    }

    return count;
}

Answer 14

def solution1(A):
    indneg = -1
    lena = len(A)
    lneg = list()
    lpos = list()

    for i in range(lena-1):
        if A[i] != A[i+1]:
            if A[i] < 0:
                lneg.append(A[i])
            else:
                lpos.append(A[i])
    print(lneg)
    print(lpos)

    deltalen = 0

    for i in lneg:
        if -i in lpos: deltalen +=1

    return(len(lneg)+len(lpos)-deltalen)

Answer 15

Binary search based solution

import java.util.Arrays;

public class AbsoluteDistinct {

    private int absoluteDistinct(int[] a) {
        if (a.length == 0 || a.length == 1) return a.length;

        Arrays.sort(a);

        int dist = 1;
        int N = a.length;
        for (int i = 0; i < N; i++) {
            if (i + 1 == N) break;
            int temp = Math.abs(a[i]);
            if (temp == Math.abs(a[i+1])) continue;
            if (Arrays.binarySearch(a, (i + 1), N, temp) < 0) dist++;
        }
        
        return dist;
    }


    public static void main(String[] args) {
        //generate array of 1 Million random values
        int LIMIT = 1000000;
        int[] a = new int[LIMIT];
        for (int i = 0; i < LIMIT; i++) {
            int r = (int) (Math.random() * (LIMIT + LIMIT + 1)) - LIMIT;
            a[i] = r;
        }
        //print absolute distinct numbers 
        System.out.println(new AbsoluteDistinct().absoluteDistinct(a));
    }
}

Answer 16

Here is my ruby version 100/100 test on codility, based on the codility test cases, an array with identical absolute values [3,-3] or [3,3] should return 1, here is the example list link

def absolute(a)
    b = Hash.new(0)
    a.each do |x|
        x = x.abs
        b[x] += 1
    end 
    return b.size
end 

Answer 17

Here is python implementation: Might not be too different from the accepted solution, but it based on two pointers idea.

def distinct(items):
    l=0
    r=len(items)-1
    count=len( set( [abs( items[l] ),abs( items[r] )] ) )
    a=1
    b=r-1
    while(a<b):
        if items[a]==items[l]:
            a+=1
        elif items[b]==items[r]:
            b-=1
        elif abs(items[a])==abs(items[b]):
            count+=1
            l=a
            r=b
            a+=1
            b-=1
        else:
            count+=2
            l=a
            r=b
            a+=1
            b-=1
    if(abs(items[a])!=abs(items[l]) and abs(items[a])!=abs(items[r]) and abs(items[b])!=abs(items[l]) and abs(items[b])!=abs(items[r])):
        count+=1
    return count

Answer 18

Here is C++ code for both implementations with code that generates a randomly sorted integer vector:

#include <vector>
#include <set>
#include <iostream>
#include <random>
#include <cstdlib>
using namespace std;
int main(int argc, char** argv) {

    // generate a vector with random negative and positive integers, then sort it
    // vector<int> vQ2{ -5, -4, -4, -2, 0, 3, 4, 5, 5, 7, 12, 14};
    vector<int> vQ2;
    std::default_random_engine e;
    std::uniform_int_distribution<> d(-10, 10);
    std::function<int()> rnd = std::bind(d, e);
    for(int n=0; n<10; ++n)
        vQ2.push_back(rnd());
    sort(vQ2.begin(),vQ2.end());

    // set (hashfunction) solution (hash)
    set<int> sQ2;
    for_each(vQ2.cbegin(),vQ2.cend(),[&sQ2](const int input) -> void { sQ2.insert( std::abs(input) ); } );
    cout << sQ2.size() << endl;

    // pointers-meeting-in-the-middle solution        
    int absUniqueCount = 0;
    vector<int>::iterator it1 = vQ2.begin();
    vector<int>::iterator it2 = prev(vQ2.end());
    int valueIt1Prev = *it1;
    int valueIt2Prev = *it2;
    while(valueIt1Prev <= valueIt2Prev)
    {
        ++absUniqueCount;
        while(valueIt1Prev == *it1 && abs(valueIt1Prev) >= abs(valueIt2Prev))
        {   advance(it1,1); } // using advance in case of non contiguous memory container (e.g. list)
        while(valueIt2Prev == *it2 && abs(valueIt2Prev) >= abs(valueIt1Prev))
        {   advance(it2,-1); } 
        valueIt1Prev = *it1;
        valueIt2Prev = *it2;
    }
    copy(vQ2.cbegin(),vQ2.cend(),ostream_iterator<int>(cout,",")); cout << endl;
    cout << absUniqueCount << endl;

    return 0;
}

Which gives:

6
-9,-8,-8,-8,-5,0,4,4,6,6,
6

Answer 19

JavaScript: 100/100

function solution(A) {
    var count = 1,
        len = A.length,
        S = A.map(function(x){ return Math.abs(x) }).sort();

    for(var i=1;i<len;i++) {
        if(S[i] != S[i-1]) count++;        
    }

    return count;
}

Answer 20

100/100 Java O(N)

public class Distinct {

    public static int solution(int[] A) {

        Set<Integer> set = new HashSet<>();
        for (int i : A) {
            set.add(i);
        }
        return set.size();
    }
}

Answer 21

Java 100/100 https://codility.com/demo/results/demoMTWUSD-S9M/

A O(N) solution without using sets and without using Sort, inspired by the Programming Pearls book, Chapter 1:

public int solutionWithoutSetCountUntilInputLength(int[] A) {
       int length = A.length;
       int inputLimit = 1000000;
       int[] positives = new int[inputLimit];
       int[] negatives = new int[inputLimit]; // should be length - 1 not counting zero

       for (int element : A) {
           if ( element >=0 ) {
               ++positives[element];
           } else {
               int abs = element * -1;
               ++negatives[abs];
           }
       }

       int countDistincts = 0;

       for (int i: A) {
           if (i >= 0 ) {
               if ( positives[i] >= 1 ) {
                   ++countDistincts;   
                   positives[i] = 0;
               }
           } else {
               if ( negatives[i * -1] >= 1 ) {
                   ++countDistincts;   
                   negatives[i * -1] = 0;
               }
           }
       }        
       return countDistincts ;
   }

I was thinking of improving the last answer, is I did some research of Bit operations with Java, and I found the next solutions with for me it performs better, it uses less space and less CPU cycles:

import java.util.Set;

public class Distinct {
public int solution(int[] A) {
        // first part for negatives, second part for positives and adding 1
        // to count the zero as part of the positives section
        int offset = 1_000_000;
        BitSet bitSet = new BitSet( (offset * 2) + 1 );

        for (int element : A ) {
            int index = element >= 0 ? offset + element : (element * -1);
            bitSet.set(index);
        }

        return bitSet.cardinality();
    }
}

Here's the codility link 100/100: https://codility.com/demo/results/demoN57YUC-G9Z/

You can see my other attempts here: Distinct

Answer 22

Very easy to do in Scala:

object Solution {
    def solution(A: Array[Int]): Int = {

        return(A.map(v => math.abs(v)).distinct.length)
    }
}

Here's link to test.

Answer 23

//java code scored 100/100 
class Solution{
public int solution(int[] A){
int distinct = 0;
Arrays.sort(A);
    if (A.length == 0){
        distinct= 0;
       }
    else{
        distinct= 1;
    }

 for(int i=1; i<A.length;i++){
    if(A[i] == A[i-1]){continue;}
    else {
    distinct +=1;
    }
}
return distinct;
}
public static void main(String[] args){
int A [] = {2,1,1,2,3,1};
System.out.println(solution(A));

}
}

Answer 24

This is my c# solution which got 100/100 for performance and correctness. It provides a simple solution to the problem.

using System;

class Solution {
    public int solution(int[] A) {
        int arrLength = A.Length;

        Array.Sort(A);

        int[] arrNegative = new int[1000002];

        int[] arrPositive = new int[1000002];

        int i,counter = 0,holder = 0;

        bool zero = false;

        for (i=0; i < arrLength; i++){     
            if(A[i]<0){
                holder = Math.Abs(A[i]);
                if(arrNegative[holder]==0) arrNegative[holder] = holder;   
            }
            else{
                if(A[i]==0) zero = true;

                if(arrPositive[A[i]]==0) arrPositive[A[i]] = A[i];
            }
        }

        foreach(int c in arrNegative){
            if(c!=0) counter++;
        }

        foreach(int c in arrPositive){
            if(c!=0) counter++;
        }

        if(zero) counter++;

        return counter;
    }
}

Answer 25

A more Catterpalistic C# solution with 100/100 score.

Got tips from below link. https://codesays.com/2014/solution-to-abs-distinct-by-codility/

 using System;

class Solution {
public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    var head = 0; 
    var tail = A.Length -1;
    var absCount = 1;
    var current = A[0] > 0 ? A[0] : -A[0];
    while(head <= tail)
    {
        var former = A[head] > 0 ? A[head] : -A[head];
        if(former == current)
        {
            head ++;
            continue;
        }

        var latter = A[tail] > 0 ? A[tail] : -A[tail];
        if(latter == current)
        {
            tail--;
            continue;
        }

        if(former >= latter)
        {
            current = former;
            head ++;
        }
        else 
        {
            current = latter;
            tail--;

        }

        absCount++;
    }

    return absCount;
}

}

Answer 26

Your solution is at least one of the easiest way to do it (more readable, easier to maintain). It surely is not the most efficient one (neither the worst) and should be acceptable if not used in a time critical code.

But you should have mentioned that and suggested that there is a more efficient solution like traversing the list from both ends (as already answered). Maybe you would have got an extra point for discussing the advantages of both solution.

Tested your solution (on old (slow) laptop):

• less than 2 milliseconds for 10000 numbers
• ~450 ms for 1000000

Answer 27

Very simple and straightforward with Java 8.

return (int) Arrays.stream(A).map(Math::abs)
            .distinct().count();

Answer 28

public static int solution(int[] A) {

      Map<Integer, Long> map= Arrays.stream(A).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting()));
      int size=map.entrySet().size();
      return size;
    }

Answer 29

I would like to share the explanation of my algorithm and C++ implementation with you.

Caterpillar mathod

1. Set the back index to the left end.

2. Set the front index to the right end.

3. Skip duplicated values at any point on both ends.

4. If the absolute value on the left is greater than the absolute value on the right, then increase the back index.

5. If the absolute value on the right is greater than the absolute value on the left, then decrease the front index.

6. If the absolute value on the right equals to the absolute value on the left, then increase the back index and decrease the front index.

7. Continue this until we have processed all the elements. This will happen when the last element is processed. This is in worst case when the back and front indices have the same value and/or element. Handle this final element and then exit the iteration.

The runtime complexity is O(N) since we go through over each element in the input array.

The space complexity is O(1) because we do not have any additional array or set, like we would have with the trivial unordered_set solution. So, whilst this approach maintains the same runtime complexity, the space complexity is more efficient.

int solution(vector<int> &A)
{                  
  int N = A.size();           
  int distinct_abs_values = 0;                                             
  for (int back = 0, front = N - 1; back <= front; ++distinct_abs_values) {
    while (back < N - 1 and A[back] == A[back + 1]) ++back;
    while (front > 0 and A[front] == A[front - 1]) --front;
                                     
    const uint64_t eb = abs(A[back]); 
    const uint64_t ef = abs(A[front]);
                        
    if (eb > ef) ++back;      
    else if (eb < ef) --front;             
    else if (eb == ef) { ++back; --front; }
  }
                             
  return distinct_abs_values;
}

Answer 30

Please find below implementation which is even much faster than Peter's.

if (A == null || A.length == 0) {
  return 0;
} else if (A.length == 1 || A[0] == A[A.length - 1]) {
  return 1;
}

int absDistinct = 0;
int leftCurrent;
int leftNext;
int rightCurrent;
int rightPrevious;

for (int i = 0, j = A.length; i < j; ) {

  leftCurrent = A[i];
  rightCurrent = A[j];
  leftNext = A[i + 1];
  rightPrevious = A[j - 1];

  if (leftCurrent + rightCurrent == 0) {
    while (A[i] - A[i + 1] == 0) {
      i++;
    }
    while (A[j] - A[j - 1] == 0) {
      j--;
    }
    i++;
    j--;
    absDistinct++;
  } else {
    if (leftCurrent + rightCurrent < 0) {
      if (leftCurrent - leftNext != 0) {
        absDistinct++;
      }
      i++;
    } else {
      if (rightCurrent - rightPrevious != 0) {
        absDistinct++;
      }
      j--;
    }
  }
}

return absDistinct;

The distribution of numbers is important. But if there will be lot of series of the same numbers this algo will perform better. This shows that the algorythms complexity is not the only barier to overcome. When you have the algo with the propper complexity this might be just one of the options. Linear correction of the algo is still possible. The character of input is sometimes also important.

Answer 31

Here is a recursive algorithm that will return the absolute unique entries in a list in a single pass, that is in O(n) time. It relies on the fact that the array is sorted and it is not using a java.util.Set.

Consider this example array {-5,-5,-3,0,1,3}

• Because the array is sorted, one of the two elements at either end of the array will have the absolute highest value: -5
• Again because the array is sorted, if that element is going to have a match, it will be its neighbour, or neighbours for multiple matches.
• So for -5 we do a single check with its neighbour: they are equal. -5 is a duplicate, so remove it, don't increase our running total and recurse.

{-5,-3,0,1,3} Now we pick -5, its unique therefore increase running total to 1 and then remove it.

{-3,0,1,3} If they two ends have equal absolute values, just remove one, it doesnt matter which, just so long as its just one. Say the first. We don't increment our running total because the value we removed was a duplicate.

{0,1,3} Now we pick 3, its unique, running total goes to 2.

{0,1} Pick 1, its unique, running total 3.

{0} Size is 1, the value is unique, increment running total and return it. 4 Correct!

package com.codility.tests;

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

public class AbsDistinct {

/**
 * Count the number of absolute distinct elements in an array.
 * The array is sorted in ascending order.
 */
private static int countAbsDistinct(List<Integer> list, int count) {
    int lastIndex = list.size() - 1;
    if (lastIndex == -1) { // zero size list, terminate
        return 0;
    }
    if (lastIndex == 0) { // one element list, terminate
        return ++count;
    }
    if (Math.abs(list.get(0)) == Math.abs(list.get(lastIndex))) {
        // doesn't matter which end is removed, but to remove _only_ 1
        list.remove(0);
    } else if (Math.abs(list.get(0)) > Math.abs(list.get(lastIndex))) {
        // if different to its nighbour, its unique hence count it
        if (list.get(0) != list.get(1)) {
            count++;
        }
        // now that its been accounted for, remove it
        list.remove(0);
    } else {
        // same logic but for the other end of the list
        if (list.get(lastIndex) != list.get(lastIndex - 1)) {
            count++;
        }
        list.remove(lastIndex);
    }
    return countAbsDistinct(list, count);
}

public static void main(String[] args) {
    if (args.length == 0) { // just run the tests
        List<Integer> testList = new ArrayList<Integer>(Arrays.asList(-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8));
        List<Integer> empty = new ArrayList<Integer>();
        List<Integer> singleElement = new ArrayList<Integer>(Arrays.asList(1));
        List<Integer> sameElement = new ArrayList<Integer>(Arrays.asList(1, 1, 1, 1, 1, 1));
        System.out.println("test array: " + countAbsDistinct(testList, 0));
        System.out.println("empty array: " + countAbsDistinct(empty, 0));
        System.out.println("single element array: " + countAbsDistinct(singleElement, 0));
        System.out.println("same element array: " + countAbsDistinct(sameElement, 0));
    } else {
        List<String> argStringList = new ArrayList<String>(Arrays.asList(args));
        List<Integer> argList = new ArrayList<Integer>();
        for (String s : argStringList) {
            argList.add(Integer.parseInt(s));
        }
        System.out.println("argument array: " + countAbsDistinct(argList, 0));
    }
}
}

Answer 32

here is a python proposal i just did to practice:

def abs_distinct(A):
    if not A:
        return -1
    #assume A is sorted
    n = len(A)
    left_cursor = 0
    right_cursor = n-1
    left_value = A[0]
    right_value = A[n-1]
    nb_abs_distinct = len(set([abs(left_value),abs(right_value)]))

    while left_value != right_value:
        # case 1: decrease right_cursor down to the next different value
        if abs(left_value) < abs(right_value):
            while A[right_cursor] == right_value:
                right_cursor -= 1
            right_value = A[right_cursor]
            if abs(right_value) != abs(left_value):
                nb_abs_distinct += 1
        # case 2: increase left_cursor to the next different value
        elif abs(left_value) > abs(right_value):
            while A[left_cursor] == left_value:
                left_cursor += 1
            left_value = A[left_cursor]
            if abs(left_value) != abs(right_value): 
                nb_abs_distinct += 1

        else:
            while abs(left_value) == abs(right_value):
                left_cursor += 1
                left_value = A[left_cursor]
            nb_abs_distinct += 1

    return nb_abs_distinct

Answer 33

int[] arr= new int[]{-5,-5,-6,-6,-6};
Set<Integer> newSet = new HashSet<Integer>();
for(int i=0;i<arr.length;i++)
  newSet.add(Math.abs(arr[i]));    

System.out.println(newSet.size());

Answer 34

Well, to be absolutely honest, you need to do better than this.

Judging from the question, I assume the list do not contain duplicates. Again, obviously the trick is the pre-sorted list. Which means that while +5 may be at the right end of the line, -5 will be at the left end of the line, since negative numbers sort in reverse to their absolute magnitude.

Start from both ends, work inwards. If the two numbers are -1 of each other, then it is not distinct. Otherwise, they are distinct, and move the end that is absolutely larger.

Go until you reach zero, or you bump into the next list -- in that case, take everything remaining in the next list as distinct as well.

This algorithm needs no hashes, no dictionaries, no data structures, and runs in O(n) time, going through the whole list exactly once.

Answer 35

The solution is to use the fact that the array is sorted. What you can do is to have two pointers pointing at beginning and end of the array respectively. Then based on the abs value, decrease/increase the end-pointer/beginning pointer. At the same time you'll have to keep track of repeated elements in sequence like {3,3,3,4} (the 3 should be counted once).

In all it wouldn't be too complex, I think with 20-25 loc in C.