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

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

**Analysis**:
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.

Why is it so hard to find a job?

ReplyDelete"שלמה קוגן"

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

ReplyDeleteThanks for your good finding. It's been fixed.

DeleteThis is purely wrong, counting numbers does not work.

ReplyDeletetry: 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

that's what I would think.

Deletethat's what I would think.

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

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

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

ReplyDeleteThat won't work.

Delete1+5+5+2 = 13

1+5+5 = 11

13-11 = 2: therefore, according to your method, the duplicated int is 2.

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.

ReplyDeleteAndroid training in chennai

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.

ReplyDeleteCCNA Training in Chennai

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.

ReplyDeleteDigital Marketing Company in Chennnai

Your while loop is missing an opening curly brace

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

ReplyDeleteThanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing

ReplyDeletedot net training in chennai

php training in chennai

java training in chennai

very nice and informative blog

ReplyDeletebig data projects chennai

mobile computing projects chennai

cloud computing projects chennai

secure computing projects chennai

Thanks for sharing this valuable information.

ReplyDeletematlab projects in chennai

You might be qualified to get a free

ReplyDelete$1,000 Amazon Gift Card.This comment has been removed by the author.

ReplyDeleteWhat 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?

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

ReplyDeleteThanks for the post!

ReplyDeleteC# Programming | C# Programming - Array

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