Java + Count duplicates from int array without usi

Question

As a part of the Java interview question paper I have got following issue to solve. But I am bit wonder whether how can I implement it without any Collection or intermediate Array.

Question:- Count duplicates from int array without using any Collection or another intermediate Array

Input values:- {7,2,6,1,4,7,4,5,4,7,7,3, 1}  

Output:- Number of duplicates values: 3
         Duplicates values: 7, 4, 1

I have implemented following solution but was not completed one. Any one has some idea? Thanks.

public static void duplicate(int numbers[]) {

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

        boolean duplicate = false;
        int j = 0;

        while (j < i){

            if ((i != j) && numbers[i] == numbers[j]) {
                duplicate = true;
            }

            j++;
        }

        if (duplicate) {
            System.out.print(numbers[i] + " ");
        }
    }
}

Answer 1

Keeping one extra variable for maintaining count, plus sorting of array in the initial phase.

public static void main(String[] args) {
        int[] numbers = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 };
        Arrays.sort(numbers);
        System.out.println("Sorted Array is :: = " + Arrays.toString(numbers));

        int count = 0;
        int tempCount = 0; // to keep local count of matched numbers
        String duplicates = "";
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == numbers[i - 1]) {
                if ((tempCount == 0)) { // If same number is repeated more than
                                        // two times, like 444, 7777
                    count = count + 1;
                    tempCount = tempCount + 1;
                    duplicates = duplicates.concat(Integer.toString(numbers[i])
                            + ",");
                }
            } else {
                tempCount = 0;
            }
        }

        System.out.println("No of duplicates :: = " + count);
        System.out.println("Duplicate Numbers are :: = " + duplicates);
    }

output

Sorted Array is :: = [1, 1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7]
No of duplicates :: = 3
Duplicate Numbers are :: = 1,4,7,

Answer 2

Agreed to Tim @tim-biegeleisen. Just minor change. Use the Arrays to sort the array.

public class DuplicateClass {

public static void main(String[] args) {
    int[] values = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 };
    duplicate(values);
}

public static void duplicate(int numbers[]) {
    Arrays.sort(numbers);
    int previous = numbers[0] - 1;
    ;
    int dupCount = 0;

    for (int i = 0; i < numbers.length; ++i) {
        if (numbers[i] == previous) {
            ++dupCount;
        } else {
            previous = numbers[i];
        }
    }
    System.out.println("There were " + dupCount + " duplicates in the array.");
}

}

Answer 3

This is the simplest solution I can think of. I just added an extra counter so that integers with two or more repetitions still in the array are ignored.

static int findNumber(int[] arr) 
{  
    int duplicateCounter = 0;

    System.out.print("Duplicates: ");

    for(int i = 0; i < arr.length; i++)
    {
        boolean duplicate = false;
        int numOfOccurrences = 1;

        for (int j = (i+1); j < arr.length; j++)
        {
            if (arr[i] == arr[j])
            {
                numOfOccurrences++;
                duplicate = true;
            }
        }
        if(numOfOccurrences == 2 && duplicate == true)
        {
            duplicateCounter++;
            System.out.print(arr[i] + " ");
        }
    }

    return duplicateCounter;
}

My test run: Test run

Input: 1, 2, 3, 4, 2, 4, 1, 1, 1

Duplicates: 2 4 1

Number of duplicates: 3

Answer 4

These are all great answers. One other is to use an int/double and set it's bits when you encounter a number. This works if the array's values are less than 32/64 depending on the type you use.

Below is an example of how you would do that with an integer.

public class SetThoseBits{

    // 0000 0000 0000 0000 000 0000 0000 0000
    public static int data = 0; 

    public static void main(String [] args){

        // Gurantee that the numbers are less than 32
        int[] values = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 };
        duplicates(values);

    }

    public static void duplicates(int [] values){

        for(int i : values){

            if(testBit(i)){
                System.out.println("Duplicate :" + i);
            } else{
                setBit(i);
            }
            //printBits();
        }

        System.out.println("Finished!");
    }

    // Sets the bit at a specific position
    public static void setBit(int index){
        data = data | (1 << index);
    }

    // This function will test the bit at the index of the given integer
    // If it's set, it returns true
    public static boolean testBit(int index){
        return ((data & (1 << index)) != 0);
    }

    public static void printBits(){

        for (int x = 31; x >= 0; x--){
            if(testBit(x)){
                System.out.print("1");
            } else{
                System.out.print("0");
            }
        }
        System.out.println("0");
    }

}

I believe the the other answers are better given your question..but demonstrating this as an alternative shows that you're thinking about it dynamically. If the requirements of the question changed a little this answer might be more appropriate.

Further if you only need to keep track of duplicates given the smallest footprint possible, you could do something similar to what is above or use java's BitSet class to make your life easier.

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

Edit: It is also possible to have values higher than 64 given that you create a function that holds an array of bytes like the BitSet class. For this exact question this isn't helpful given the constraint to not use an array or collection.

Answer 5

    int numbers[]={7,2,6,1,4,7,4,5,4,7,7,3, 1};
    String temp="";
    int count=0;
    Arrays.sort(numbers);

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

        boolean duplicate = false;
        for(int j = 0; j < numbers.length; j++) {
            if ((i != j) && numbers[i] == numbers[j]) {
                duplicate = true;
            }
        }

        if (duplicate) {
            if(!temp.contains(""+numbers[i]))
            {
            temp+=numbers[i]+", ";//adding a number if its duplicate
            count++;//counting unique duplicate number
            }
            System.out.print(numbers[i] + " ");
        }
    }
    System.out.println("\nDuplicates are: "+temp+" count: "+count);

Output:

 Duplicates are: 1, 4, 7,  count: 3

Answer 6

There is one method where you can use Math.abs. You should check for the sign positive.If it is positive then make it negative. If negative then that's the duplicated number or the repeated number. Example: A[] = {1, 1, 2, 3, 2} i=0; Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative. Array now becomes {1, -1, 2, 3, 2}

i=1; Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition. Then just put all those repeated numbers into a list and print the size of the list.

The code in python is

    from astropy.extern.ply.cpp import xrange
def printrepeat(arr):
    print("The repeating elements are: ")
    list =[]
    for i in xrange(0,len(arr)):
        ch = abs(arr[i])

        if arr[ch] > 0:
            arr[ch] = (-1)*arr[ch];

        else: list.append(arr[ch])

    print(len(list))    




# driver code

arr = [1 , 3 , 2 , 2 , 1,3]
printrepeat(arr)            

Solution 2: Taking 2 pointers

class Abc1{
    public static void main(String[] args) {

   int[] a = {1, 1, 2, 3, 2};
   countDuplicates(a);
}

    private static void countDuplicates(int[] a) {
        int c = 0 ;
        for(int  i = 0 ; i < a.length ; i++) {

            for(int j = i+1 ; j < a.length;j++) {
                if(a[i] == a[j]) {c++ ;}
            }//for
        }//for1
        System.out.println("dup => " + c);
    }

}

Solution 3: HashSet

class Abc1{
    public static void main(String[] args) {

  String a = "Gini Gina Protijayi";
   countDuplicates(a);
}

    private static void countDuplicates(String aa) {
        List<Character> list= new ArrayList<>();
       Set<Character> set = new HashSet<>();
       // remove all the whitespaces 
       String a = aa.replaceAll("\\s+","");
       for(  char ch : a.toCharArray()) {

           if(!set.contains(ch)) {
               set.add(ch);
           }//if
           else {if(!list.contains(ch) ) {list.add(ch);}      }
       }//for
       System.out.println("number of duplicate characters in the string =>" + list.size());
       System.out.println(list);
    }

}

Solution:4(same concept as solution 1 but code is in Java)

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

public class AA {

    public static void main(String[] args) {
         int a[] = {4, 2, 4, 5, 2, 3, 1};
         printRepeat(a);


    }

    private static void printRepeat(int[] a) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if( a[Math.abs(a[i])]  > 0) {
                a[Math.abs(a[i])] = (-1)*  a[Math.abs(a[i])] ; 
            }//if
            else {
                System.out.println( "Duplicate numbers => " + Math.abs(a[i])         );
                list.add(Math.abs(a[i]));
                System.out.println("list => " + list);
                System.out.println("list.size() or the count of duplicates => " + list.size());
            }//else

        }//for

    }//print
    }