## 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.

1. Why is it so hard to find a job?
"שלמה קוגן"

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

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

3. 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

1. that's what I would think.

2. that's what I would think.

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.

4. 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.

5. 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.

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.

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

6. 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

7. 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

8. 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

9. Your while loop is missing an opening curly brace

10. 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.

11. 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

12. Thanks for sharing this valuable information.
matlab projects in chennai

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

14. This comment has been removed by the author.

15. 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?

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

17. Thanks for the post!
C# Programming | C# Programming - Array

18. 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.

19. 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

20. 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

21. 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.

22. This comment has been removed by the author.

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

24. 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.

25. 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

26. 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.

27. Wonderful blog.. Thanks for sharing informative Post. Its very useful to me.

Installment loans
Payday loans
Title loans

28. Hi dear,  the approach of your blog is very good, the information is accurate thanks for such relevant information if you want to know more about Post Free Ads here is another classified webite https://www.helpadya.com .

29. This is such a great blog that you've posted and you give it for free. I like seeing blog that understand the value of providing a quality resource for knowledge. Thanks for sharing it very useful for Help Adya to Post Free Ad.

30. Hi dear,  the approach of your blog is very good, the information is accurate thanks for such relevant information if you want to know more about Post Free Ads here is another classified webite https://www.helpadya.com .

31. I found some useful information in your blog, it was awesome to read, thanks for sharing this great content to my vision, keep sharing.

Financial Accounting Homework Help

32. Thanks for posting your valuable thoughts with us & our readers. Please keep continue writing on this blog.
Bulk SMS Service Provider

33. Very amazing blog on a fresh new topic. I am definitely going to use the information provided in this blog because of its novel and fresh. Thanks for sharing such valuable information with everyone.
Website Development Company Bangalore
Website Design and Development Companies in Bangalore
eCommerce Website developers in bangalore
Outsource magento ecommerce services india

34. Nice and informative article.
I am preparing from mettl.com for Coding. It really helps.