CODEWITHSUNDEEP
javaarrayscollectionsduplicates
Channa
Channa

Reputation: 5233

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

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

Upvotes: 13

Views: 73949

Answers (12)

Anil Konduru
Anil Konduru

Reputation: 1008

public static void main (String args[]) {

int[] nums = {1,2,3,5,2,9,1,2,3,5,2,9};

    
    /** Expected output
    9-->2
    1-->2
    2-->4
    3-->2
    5-->2 
    **/
    
    Map<Integer, Integer> map = new HashMap<>(5);
    int arrayLength = nums.length;
    while(arrayLength > 0) {
        System.out.println(Arrays.toString(nums));
        int numToCompare = nums[arrayLength-1];
        map.put(numToCompare, 0);
        for(int i=0; i < nums.length; i++) {
            if(nums[i] == numToCompare) {
                map.put(numToCompare, map.get(numToCompare) + 1);
            }
        }
        arrayLength--;
    }
    for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
        System.out.println(entry.getKey() + "-->" + entry.getValue());
    }
}

Upvotes: 0

Soudipta Dutta
Soudipta Dutta

Reputation: 2122

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

Upvotes: 0

Azamat Toshtemirov
Azamat Toshtemirov

Reputation: 31

 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();
}

Upvotes: 1

Mukesh Kumar
Mukesh Kumar

Reputation: 985

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

Upvotes: 4

Mayank Shekhar
Mayank Shekhar

Reputation: 11

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);
  }
}

Upvotes: 0

Lampard
Lampard

Reputation: 404

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;
}

Upvotes: 0

jaymaytay
jaymaytay

Reputation: 1

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

Upvotes: 0

user5778069
user5778069

Reputation:

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);
    }
}

Upvotes: 0

Pumphouse
Pumphouse

Reputation: 2053

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.

Upvotes: 1

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521249

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.

Upvotes: 11

SatyaTNV
SatyaTNV

Reputation: 4135

    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

Upvotes: 0

Ankur Singhal
Ankur Singhal

Reputation: 26067

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,

Upvotes: 0

Related Questions