Java + Count duplicates from int array without using any Collection or another intermediate Array

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] + " ");
        }
    }
}

May be duplicate http://stackoverflow.com/questions/17967114/how-to-efficiently-remove-duplicates-from-an-array — Rafiq, Jul 31 '15 at 05:42
You can use an array to store the duplicate values as in your demonstrated output? — milez, Jul 31 '15 at 05:43

Tim Biegeleisen · Accepted Answer · 2015-07-31T09:36:55.250

The easiest way to solve this problem is to sort the array first, and then just walk through the array counting duplicates as you encounter them:

int[] numbers = new int[]{7,2,6,1,4,7,4,5,4,7,7,3,1};
int temp = 0;

// I chose to do a bubble sort of the array,
// but you are free to use any method you wish (e.g. Arrays.sort)
System.out.print("Duplicates values: ");
for (int i=0; i < numbers.length; ++i) {
    for (int j=1; j < (numbers.length - i); ++j) {
        if (numbers[j-1] > numbers[j]) {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
        }
    }
}


// walk through the sorted array and count duplicates
int numDup = 0, dupCount = 0;
int previous = -1;
for (int i=0; i < numbers.length; ++i) {
    if (numbers[i] == previous) {
        ++numDup;
        if (numDup == 1) {
            ++dupCount;
            if (dupCount == 1) {
                System.out.print(numbers[i]);
            }
            else {
                System.out.print(", " + numbers[i]);
            }
        }
    }
    else {
        previous = numbers[i];
        numDup = 0;
    }
}

System.out.println("\nNumber of duplicates values: " + dupCount);

Output:

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

Note that my output order is reverse of what you have, because you need to read through the entire array before you know how many total duplicates you have. Also, I will point out that the only state this solution uses is the input array itself, plus a couple of int varibles here and there.

This code has been tested in IntelliJ and it works correctly.

score 4 · Answer 2 · edited Dec 07 '20 at 02:39

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

import java.util.*;
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.");
    }
}

Pumphouse · Answer 3 · 2015-07-31T17:46:41.807

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.

This is an interesting idea. Can you provide some Java code which implements this? — Tim Biegeleisen, Jul 31 '15 at 09:36
@TimBiegeleisen I apologize that it took so long, but here is a working example on how you would do that. The printBits() function is just so that you can see how the bits are changing. — Pumphouse, Jul 31 '15 at 17:42

score 1 · Answer 4 · answered Dec 04 '21 at 06:17

 private static int solution3(List<Integer> inputArr) {
    // Time Complexity O(N)
    // Space Complexity O(1)
    // Stream
    return (int) inputArr.stream()
            .collect(Collectors
                    .toMap(Function.identity(), v -> 1, Integer::sum))
            .entrySet().stream()
            .filter(k -> k.getValue() >= 2)
            .count();
}

SatyaTNV · Answer 5 · 2015-07-31T06:09:18.450

    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

score 0 · Answer 6 · answered Jul 31 '15 at 05:56

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,

score 0 · Answer 7 · 2016-12-12T11:32:29.010

I think, this is also a way to calculate it:

public class App {
    public static void main(String[] args) {
        Integer[] intArr = { 7, 2, 6, 1, 4, 7, 4 };
        List<Integer> listInt = Arrays.asList(intArr);

        Map<Integer, Integer> map = new HashMap<>();
        Integer dupCount = 0;
        StringBuilder dupvalues = new StringBuilder();

        for (Integer integer : intArr) {
            int times = Collections.frequency(listInt, integer);
            if (map.containsKey(integer)) {
                dupvalues.append(integer).append(",");
                dupCount++;
            } else
                map.put(integer, times);
        }
        System.out.println("There were " + dupCount + " duplicates in the array. The value are : "+dupvalues);
    }
}

score 0 · Answer 8 · answered Oct 25 '17 at 03:55

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

Lampard · Answer 9 · 2018-12-03T09:48:14.093

Below method not use any collection, just use Arrays.sort() method to help sort array into ascending order as default, e.g array = [9,3,9,3,9] will sort into [3,3,9,9,9].If input [9,9,9,9,9], expected result is 1, since only repeated number is 9.If input [9,3,9,3,9,255,255,1], expected result is 3, since repeated numbers are 3,9,255. If input [7,2,6,1,4,7,4,5,4,7,7,3,1], expected result is 3, since repeated numbers are 1,4,7.

public static int findDuplicateCountsInArray(int[] nums) {
    // Sort the input array into default ascending order
    Arrays.sort(nums);
    int prev = nums[0];
    int count = 0;
    // Recording a number already a repeated one
    // e.g [9,9,9] the 3rd 9 will not increase duplicate count again
    boolean numAlreadyRepeated = false;
    for(int i = 1; i < nums.length; i++) {
        if(prev == nums[i] && !numAlreadyRepeated) {
            count++;
            numAlreadyRepeated = true;
        } else if(prev != nums[i]) {
            prev = nums[i];
            numAlreadyRepeated = false;
        }
    }
    return count;
}

score 0 · Answer 10 · edited Jun 02 '19 at 20:24

Here I have written code in JAVA. also the inputted numbers, have been considered as String. This question has also been added to CODEWARS. and I hope this simple solution helps You

public class countingduplicates {
  public static void main(String[] args) {
    int i=0,j=0,c=0,a=0;
    String text="7261474547731";
    text=text.toLowerCase();

    for(i=0; i<text.length(); i++) {
      for(j=0; j<text.length(); j++) {
        if(text.charAt(i) == text.charAt(j)) { 
          c++;
        }
      }

      System.out.println(text.charAt(i) + " occured " + c + " times");
      if(c>1) {
        a++;
      }  

      String d = String.valueOf(text.charAt(i)).trim();
      text = text.replaceAll(d,"");
      c = 0;
      i = 0; //cause i have trimmed the string and by default i increases by 1, so i have to assign it =0
      j = 0; //cause i have trimmed the string and by default j increases by 1, so i have to assign it =0
    }
  System.out.println("Total count of Duplicates:" + a);
  }
}

Soudipta Dutta · Answer 11 · 2022-03-29T14:04:13.680

This is practically very easy in Python. You can check this code. I am giving you 2 methods. Please take a look at it.

array = ['a','b','c','d','a','b','c','d','e']
array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5]
output = {i : array1.count(i) for i in array1 }
print(output) #{1: 1, 2: 2, 3: 3, 4: 3, 5: 5, 6: 1}

output2 = dict(Counter(array1))

print(output2) #{1: 1, 2: 2, 3: 3, 4: 3, 5: 5, 6: 1}

If you want only the Duplicate numbers, then :

#method 1
output = [k for k,v in Counter(array1).items() if v>1 ]
print(output)

If you want only the Distinct numbers, then :

 #method 1 
    #Prints only Distinct absolute values
    O2 = set([abs(i) for i in array1])
    print(O2) #1,2,3,4,5,6

Java + Count duplicates from int array without using any Collection or another intermediate Array

11 Answers11

Linked