Monday, April 4, 2016

No. 59 - Duplications in Arrays

Questions: All numbers in an array with length n+1 are in range from 1 to n, so there is at least one duplication in the array. How to find any a duplication? Please don't modify the input array.

Analysis: The simple solution is to utilize hash tables. When scanning the array, array elements are inserted into the hash table one by one. In this way, it's easy to find a duplication with the hash table, which costs O(n) space.

Let's try not to employ extra space. Why there are duplications in the array? If there are no duplications, the count of numbers ranging from 1 to n is n. Since the array contains more than n numbers, there should be duplications. It looks like it's important to count numbers in ranges.

Let's divide numbers from 1 to n into two ranges, split with the number in the middle (denoted as m), and then count the numbers of the two subranges. If the count of numbers from 1 to m is greater than m, the duplication is in the range from 1 to m. Otherwise, there should be at least one duplication in the range from m+1 to n. And then we continue the recursive process until we find the duplication.

The Java code is listed below:

static int countRange(int[] numbers, int start, int end)
{
    int count = 0;
    for(int i = 0; i < numbers.length; i++)
        if(numbers[i] >= start && numbers[i] <= end)
            ++count;
    return count;
}

static int getDuplication(int[] numbers)
{
    int start = 1;
    int end = numbers.length;
    while(end >= start)
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers, start, middle);
        if(end == start) {
            if(count > 1)
                return start;
            else
        break;
    }

    if(count > (middle - start + 1))
        end = middle;
    else
        start = middle + 1;
    }
    return -1;
}

The code with unit tests is shared at http://ideone.com/lhV22m.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this article in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

33 comments:

  1. looks like a typo, the statement "int end = numbers.length;" should be above the while loop.

    ReplyDelete
    Replies
    1. Thanks for your good finding. It's been fixed.

      Delete
  2. This is purely wrong, counting numbers does not work.

    try: int[] nums = new int[] { 9, 8, 7, 2, 2, 3, 4, 6, 1, 5 }

    Just sum all the numbers, subtract n*(n-1)/2 (sum of 1..n) and you get your answer

    ReplyDelete
    Replies
    1. that's what I would think.

      Delete
    2. that's what I would think.

      Delete
    3. The solution works only if there is exactly one duplication in the array. This is a special case for the problem here. It doesn't limit the number of duplication.

      Delete
  3. Center for Career Advice. Provides a positive Career Help for career source and encouraging website for anyone to gather the necessary tools for landing a dream job. Articles, advice, and feedback provided for free.

    ReplyDelete
  4. another solution ( I assume the elements in array are all integers): a = sum of n+1 elements, b = sum of n continuous integers, thus the duplicated integer is equal to b-a.

    ReplyDelete
    Replies
    1. That won't work.
      1+5+5+2 = 13
      1+5+5 = 11
      13-11 = 2: therefore, according to your method, the duplicated int is 2.

      Delete
    2. I think he requires contiguous integers, so for your example 1+2+3+4+5+5 = 20 while 1+2+3+4+5 should equal 15, so 20 - 15 = 5

      Delete
  5. This idea is mind blowing. I think everyone should know such information like you have described on this post. Thank you for sharing this explanation.Your final conclusion was good. We are sowing seeds and need to be patiently wait till it blossoms.
    Android training in chennai

    ReplyDelete
  6. Superb i really enjoyed very much with this article here. Really its a amazing article i had ever read. I hope it will help a lot for all. Thank you so much for this amazing posts and please keep update like this excellent article.

    CCNA Training in Chennai

    ReplyDelete
  7. wow really nice. It will be helpful for the people those who are ready to crack the interview and please also for remind what they have learned throughout concept.

    Digital Marketing Company in Chennnai

    ReplyDelete
  8. Your while loop is missing an opening curly brace

    ReplyDelete
  9. The Java complies Source Coding into a format known as "Byte-Code". The Byte-code source files is then executed by interpreter. While using arrays, we create objects for arrays where class is non-existent. Whenever JVM encounters It understands that it must create an object. Thus, array object can be created without using the new operator. Find more Tips and JAVA Homework Help in Array.

    ReplyDelete
  10. Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing
    dot net training in chennai
    php training in chennai
    java training in chennai

    ReplyDelete
  11. You might be qualified to get a free $1,000 Amazon Gift Card.

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. What is the time complexity of this solution? I guess it is O(nlogn). Complexity of countRange() is O(n) and it is invoked at most log(n) time. Is that correct?

    ReplyDelete
  14. Great information regarding job. If some one interested to find jobs in California then needs to search USA directories.

    ReplyDelete
  15. Hey guys thanks for sharing this! I love how the idea... really very nice blog. But you know Help Adya is also free classified ads posting site even much better than yours.

    ReplyDelete
  16. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.
    Manpower Consultancy in Chennai
    Hr Consultancy in Chennai

    ReplyDelete
  17. wow so nice
    and lastest update for jobs
    SBI Recruitment 2017-255 Relationship Managers, Customer Relationship Executives, Investment Counsellors Jobs in India-Starting Date 24 March & Last Date 10 April 2017
    SBI Recruitment 2017

    ReplyDelete
  18. Your blog looks very cool. Search and Find jobs in Vancouver for better career in the Canada. For free Job Postings Site in Vancouver and Search employment opportunities in Vancouver, surrey, Ontario or Free Job Postings Site in Surrey visit job posting 247.

    ReplyDelete
  19. This comment has been removed by the author.

    ReplyDelete
  20. HWB Recruitment 2017-61 Fireman, Driver jobs In Maharashtra-Last Date 25 April 2017
    http://www.sarkarinaukridekho.com/hwb-recruitment-2017/

    ReplyDelete
  21. Although this blog post was meant to help the professional coders to familiarize themselves with interview questions, it can also be applicable to other professions since the interview process is almost similar, the content is what differs. Thanks for sharing this information; I am sure it will help a lot of online users to prepare themselves adequately for the job interviews. Find time and visit my blog by clicking on Qualitative Dissertation Help and Analysis.

    ReplyDelete
  22. Thank You for such useful information, I like your blog but there is one more website which is much better for Post Free Ads  www.helpadya.com

    ReplyDelete
  23. Since you're only looking for duplicates you only need to store if they number has been seen before or not, so you could initialize a suitably large numbers of bits and use the value of the number as your offset. Initialize all the bits to zero and then scroll though your list checking each bit before you set it and if it was already been set then you have your duplicate and this won't require that the numbers be sorted and avoid large sums.

    ReplyDelete