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.

88 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
    Replies
    1. By using reflection we can create a object of any calss.with the help of class class object we can call a method newInstance() that returns a object of class

      Delete
  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
  24. Wonderful blog.. Thanks for sharing informative Post. Its very useful to me.

    Installment loans
    Payday loans
    Title loans

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

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

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

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

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

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

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

    ReplyDelete
  32. I read this article. I think You put a lot of effort to create this article. I appreciate your work.
    Dissertation Writing Services

    ReplyDelete
  33. Thanks for such important information.keep up the good work.Ethical Hacking training is based on current industry standards that helps attendees to secure placements in their dream jobs at MNCs. Indian Cyber Army Provides Best Ethical Hacking Training in India.Indian Cyber Army credibility in Ethical hacking training & Cybercrime investigation training is acknowledged across nation as we offer hands on practical knowledge and full assistance with basic as well as advanced level ethical hacking & cybercrime investigation courses

    ReplyDelete
  34. nice post...
    for more latest coding tips and tricks in hindi please visit:https://hindidea.blogspot.com

    ReplyDelete
  35. Hmm, it seems like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog. I as well as an aspiring blog writer, but I’m still new to the whole thing. Do you have any recommendations for newbie blog writers? I’d appreciate it.
    Advanced AWS Interview Questions And Answers, Top 250+AWS Interviews Questions and Answers 2018
    Advanced AWS Training in Bangalore | Best Amazon Web Services Training in Bangalore
    Advanced AWS Training in Pune | Best Amazon Web Services Training in Pune
    Best Amazon Web Services Training in Pune | Best AWS Training in Pune
    Advanced AWS Online Training | Best Online AWS Certification Course in india

    ReplyDelete
  36. Hello I am so delighted I found your blog, I really found you by mistake, while I was looking on Yahoo for something else, anyways I am here now and would just like to say thanks for a tremendous post. Please do keep up the great work.
    python course in pune
    python course in chennai
    python course in Bangalore

    ReplyDelete
  37. It was worth visiting your blog and I have bookmarked your blog. Hope to visit again
    python course in pune
    python course in chennai
    python Training in Bangalore

    ReplyDelete
  38. You are doing a good job. Really appreciate it. Check out my coding blog :)

    ReplyDelete
  39. Awesome article. It is so detailed and well formatted that i enjoyed reading it as well as get some new information too.
    Best Devops training in sholinganallur
    Devops training in velachery
    Devops training in annanagar
    Devops training in tambaram

    ReplyDelete
  40. Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.
    Best Devops Training in pune
    Data science training in pune | Data Science training institute in Pune

    ReplyDelete
  41. After seeing your article I want to say that the presentation is very good and also a well-written article with some very good information which is very useful for the readers....thanks for sharing it and do share more posts like this.
    Data Science Training in Chennai
    Data Science course in anna nagar
    Data Science course in chennai
    Data science course in Bangalore
    Data Science course in marathahalli

    ReplyDelete

  42. Whoa! I’m enjoying the template/theme of this website. It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appeal. I must say you’ve done a very good job with this.

    AWS TRAINING IN BANGALORE|NO.1AWS TRAINING INSTITUTES IN BANGALORE

    ReplyDelete

  43. Whoa! I’m enjoying the template/theme of this website. It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appeal. I must say you’ve done a very good job with this.
    aws training in bangalore
    RPA Training in bangalore
    Python Training in bangalore
    Selenium Training in bangalore
    Hadoop Training in bangalore

    ReplyDelete
  44. Amazing post with lots of informative and useful and amazing content. Well written and done!! Thanks for sharing keep posting.
    clipping path

    ReplyDelete
  45. Thanks for such a great article here. I was searching for something like this for quite a long time and at last I’ve found it on your blog. It was definitely interesting for me to read  about their market situation nowadays.
    Authorized iphone service center in Chennai | iphone service center in chennai | Mobile service center in chennai | Authorized iphone service center in Chennai | iphone service center in chennai

    ReplyDelete
  46. Thank you for such a sweet tutorial - all this time later, I've found it and love the end result. I appreciate the time you spent sharing your skills.
    Best Ice Fishing Gloves Best Ice Fishing Gloves Best Ice Fishing Gloves


    ReplyDelete
  47. A bewildering web journal I visit this blog, it's unfathomably heavenly. Oddly, in this present blog's substance made purpose of actuality and reasonable. The substance of data is informative
    Oracle Fusion Financials Online Training
    Oracle Fusion HCM Online Training
    Oracle Fusion SCM Online Training

    ReplyDelete
  48. Nội dung bài viết thật tuyệt vời. Mình cũng muốn giới thiệu về một Công ty dịch thuật uy tín - Công ty dịch thuật miền trung - MIDtrans trụ sở chính chính tại địa chỉ 02 Hoàng Diệu, TP Đồng Hới, tỉnh Quảng Bình có Giấy phép kinh doanh số 3101023866 cấp ngày 9/12/2016 là đơn vị chuyên cung cấp dịch vụ dịch thuật, phiên dịch dành các cá nhân. Hệ thống thương hiệu và các Công ty dịch thuật con trực thuộc: dịch thuật bình dương - dịch thuật miền trung tại địa 123 Lê Trọng Tấn, Dĩ An, Bình Dương là địa chỉ chuyên cung cấp dịch vụ dịch thuật chuyên nghiệp tại Bình Dương và các khu vực lân cận ; dịch thuật chuyên ngành tại sài gòn địa chỉ 47 Điện Biên Phủ, Phường Đakao, Quận 1 TP HCM, dịch thuật công chứng kon tum : địa 101 Trần Hưng Đạo, TP Kon Tum là nhà cung ứng dịch vụ dịch thuật uy tín hàng đầu tại Kon Tum; Công ty dịch thuật Viettrans và dịc vụ binh duong translation: dịch vụ dịch thuật tại Bình Dương cho người nước ngoài có nhu cầu, giao diện tiếng Anh dễ sử dụng; dịch thuật tiếng Ý (italia) tại sài gòn: nhà cung ứng dịch vụ dịch vụ dịch thuật phiên dịch hàng đầu tại TP Hồ Chí Minh; dịch thuật tiếng Anh tại Đà Nẵng : Địa chỉ 54 Đinh Tiên Hoàng, Quận Hải Châu, TP Đà Nẵng chuyên cung cấp dịch vụ dịch thuật công chứng, dịch thuật đa ngôn ngữ, đa chuyên ngành tại Đà Nẵng; Viettrans 43 Điện Biên Phủ, Quận 1 Sài Gòn: chuyên cung cấp dịch vụ dịch thuật đa chuyên ngành toàn quốc; Công ty dịch thuật Hà Nội MIDtrans chuyên cung cấp dịch vụ dịch thuật tại an giang : địa chỉ 55 Lê Thánh Tông, TP Long Xuyên là nhà cung ứng dịch vụ biên dịch, phiên dịch chuyên nghiệp tại địa bàn An Giang. Ngoài ra, Chúng tôi cũng cung cấp các dịch vụ biên dịch và phiên dịch, dịch thuật công chứng chất lượng cao hơn 50 ngôn ngữ khác nhau như tiếng Anh, Nhật, Hàn, Trung, Pháp, Đức, Nga, .vv... Dịch thuật MIDtrans tự hào với đội ngũ lãnh đạo với niềm đam mê, khát khao vươn tầm cao trong lĩnh vực dịch thuật, đội ngũ nhân sự cống hiến và luôn sẵn sàng cháy hết mình. Chúng tôi phục vụ từ sự tậm tâm và cố gắng từ trái tim những người dịch giả.Tự hào là công ty cung cấp dịch thuật chuyên ngành hàng đầu với các đối tác lớn tại Việt nam trong các chuyên ngành hẹp như: Viettravel - vietnamese tourist information and travel tips tại 46 Trần Cao Vân, TP Huế chuyên trang về thông tin du lịch và các tour đặc sắc tại Việt Nam, y dược (bao gồm bệnh lý), xây dựng (kiến trúc), hóa chất, thủy nhiệt điện, ngân hàng, tài chính, kế toán. Các dự án đã triển khai của Công ty dịch thuật chuyên nghiệp MIDtrans đều được Khách hàng đánh giá cao và đạt được sự tín nhiệm về chất lượng biên phiên dịch. Đó là kết quả của một hệ thống quản lý chất lượng dịch thuật chuyên nghiệp, những tâm huyết và kinh nghiệm biên phiên dịch nhiều năm của đội ngũ dịch giả của chúng tôi. Hotline: 0947688883. email: info@dichthuatmientrung.com.vn . Các bạn ghé thăm site ủng hộ nhé.

    ReplyDelete
  49. It proved to be Very helpful to me and I am sure to all the commentators here!
    machine learning course malaysia

    ReplyDelete
  50. If you have Natural Curls or Curly Hair, you are just blessed. You can experiment with many Hairstyles which will Look Stylish here we tell about top best and easy Curly Hairstyles and Curly Hair Tips of 2019

    ReplyDelete
  51. Very Nice Information And Beautiful Execution. I will definitely visit your Blog again. Good Work, Thank You So Much! - Job News Assam 2019

    ReplyDelete
  52. Thanks for sharing valuable information.It will help everyone.keep Post.
    Dhankesari

    ReplyDelete
  53. Дээд чанар бол зүгээр л( đá ruby thiên nhiên ) санаатай биш юм. Энэ нь өндөр( đá ruby nam phi ) түвшний төвлөрөл, тусгай хүчин( Đá Sapphire ) чармайлт, ухаалаг ( đá sapphire hợp mệnh gì )чиг баримжаа, чадварлаг туршлага, ( đá ruby đỏ )саад тотгорыг даван туулах( bán đá sapphire thô ) боломжийг хардаг.

    ReplyDelete
  54. Thanks for the Valuable information.Really useful information. Thank you so much for sharing.It will help everyone.Keep Post. Find Some Indian Memes. Interesting News Viral News Some Life hacks tips Life hacks Entertainment News Find Some Viral News Here.Viral News

    ReplyDelete
  55. I am looking for and I love to post a comment Python training in punethat "The content of your post is awesome" Great work!

    ReplyDelete
  56. I like viewing web sites which comprehend the price of delivering the excellent useful resource Python training in pune free of charge. I truly adored reading your posting. Thank you!

    ReplyDelete