Friday, October 10, 2014

No. 57 - Integer Identical to Index


Problem: Integers in an array are unique and increasingly sorted. Please write a function/method to find an integer from the array who equals to its index. For example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.
Analysis: If we scan all integers in the array from beginning to end, we may check whether every element equals its index. Obviously, this solution costs O(n) time.
Since numbers are sorted in the array, let's try to utilize the binary search algorithm to optimize. Supposing we reach the ith element in the array at some step. If the value of element is also i, it is a target integer and let's return it.
What would happen when the value m is greater than the index i? For any k (k>0), the value of element with index i+k should be greater than or equal to m+k, because integers are unique and increasingly sorted in the array. Additionally because m>i, m+k>i+k. Therefore, every element on the right side of index i should be greater than its index in such a case.
Similarly, when the value of element with index i is less than i, every integer on the left side should be less than its index. Please prove it if you are interested.
Therefore, we could reduce the search scope to half for the next step, and it is a typical process for binary search. The solution can be implemented with the following Java code:
public static int getNumberSameAsIndex(int[] numbers) {
    if(numbers == null || numbers.length == 0) {
        return -1;
    }
       
    int left = 0;
    int right = numbers.length - 1;
    while(left <= right) {
        int middle = left + ((right - left) >>> 1);
        if(numbers[middle] == middle) {
            return middle;
        }
           
        if(numbers[middle] > middle) {
            right = middle - 1;
        }
        else {
            left = middle + 1;
        }
    }
       
    return -1;
}

The source code with unit test cases is shared at http://ideone.com/ZSd9kG.
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.

71 comments:

  1. May "because m>k, m+k>i+k" should be "because m>i, m+k>i+k" ?

    ReplyDelete
    Replies
    1. Thanks for your findings. It's a typo, and been fixed.

      Delete
  2. Very good explanation about this program
    http://ccppcoding.blogspot.com/
    http://appsdevelopment-for-mobiles.blogspot.com/

    ReplyDelete
  3. It looks like there are better solutions available in the book
    Cracking Programming Interviews: 500 Questions With Solutions by Sergei Nakariakov
    http://www.amazon.com/Cracking-Programming-Interviews-Questions-Solutions/dp/1495459802/

    ReplyDelete
  4. what if the list contains more than 1 element whose value equals index? e.g.
    [-2, 1, 2, 3]

    ReplyDelete
    Replies
    1. The function which returns anyone of 1, 2, or 3 should be Ok.

      Delete
  5. Such a nice article has been posted it is very useful for computer background students.......
    Stock future tips

    ReplyDelete

  6. Thanks for the bunch of good resourceful site.I really appreciate your blog,
    you have done the great job.
    Health beauty blogs

    ReplyDelete
  7. hey your blog design is very nice,
    clean and fresh and with updated content, make people feel peace and I always like browsing your site.
    patiala jokes

    ReplyDelete
  8. You are providing outstanding news, very helpful to people plz keep it up ….we are advisory forum provides free trial ,technical news and advise health for trader.
    sign up now Commodity tips

    ReplyDelete
  9. http://www.raviparscha.com/kali-twacha-bhagaiye-gori-twacha-paiye-kale-se-gore-hone-ke-gharelu-nuskhe.html

    ReplyDelete
  10. That was an interesting and intriguing article on coding and I have learned a lot. Thanks so much foe sharing the information with us and I will be practice writing the programs shared during my free time. Check out our writing site by clicking on Case Study Editing Services.

    ReplyDelete
  11. नमस्ते दोस्तों मै अनूप अग्रवाल hindiinformations.com में आपका स्वागत करता हूँ इस ब्लॉग में मै आपको Body banane ke tarike बताऊंगा जिससे आपको आसानी होगी अपनी बॉडी बनाने में | Click here to know more दोस्तों में आपको बता दू की बॉडी बनाना बहुत ही आसान हे बस थोड़ी जरूरत हे तो सिर्फ मेहनत की जो आप करते ही होंगे पर दोस्तों आपको बता दू की बॉडी बनाने के लिए एक अच्छे डाइट प्लान की भी जरूरत होती है आज कल सभी लोग GYM में ज्यादा टाइम देते है पर आपको शायद पता नही होगा की डाइट भी एक अहम हिस्सा हे बेहतर बॉडी बनाने का , बिना अच्छे डाइट प्लान के बेहतर और अच्छी बनाना बहुत ही कठिन हे . हिंदी में अधिक जानकारी के लिए यहाँ क्लिक करे https://hindiinformations.com

    ReplyDelete
  12. Very nice post thanks for sharing with us.
    zoid research

    ReplyDelete
  13. Hi There,

    This is indeed great! But I think perhaps you are generally referring Integer Identical to Index which is getting unsustainable.

    I hate windows and want to switch to Linux (i've already tried it several times and love it), but i don't know wich linux distro to choose.
    Very useful post !everyone should learn and use it during their learning path.

    Regards,
    Preethi

    ReplyDelete
  14. Apart from a large number of various emails prevailing on the web, the Brighthouse is also a rapid email service.

    Read More:- https://www.technicalsupporttollfree.com/brighthouse-customer-support/

    ReplyDelete
  15. 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
  16. We manage your journey on all domestic and international routes for any airline, providing the very best services from our professional and Airline Ticket Reservation, Airfares and Discount Flight Prices for its smart price. LIVE Travel Experts Avail. For More info Visit-
    Delta Ticket Reservation
    Delta Ticket
    Cheap Delta Ticket

    ReplyDelete
  17. Wow! this is Amazing! Do you know your hidden name meaning ? Click here to find your hidden name meaning

    ReplyDelete
  18. خدمة كتابة السيرة الذاتية الإحترافية says
    Where to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast

    ReplyDelete
  19. Your Affiliate Profit Machine is waiting -

    And making money with it is as easy as 1...2...3!

    Here is how it works...

    STEP 1. Input into the system which affiliate products the system will push
    STEP 2. Add PUSH button traffic (it LITERALLY takes 2 minutes)
    STEP 3. See how the system grow your list and sell your affiliate products on it's own!

    So, do you want to start making profits?

    You can test-drive the system for yourself risk free...

    ReplyDelete
  20. I Found this blog very informative. keep writing.

    MCX Tips

    ReplyDelete
  21. //Hello this solution is also acceptable right? Response will be highy appreciable Here according to my solution all the conncection between the element and the index is if we do i-a[i] on the left side is positive and on the right side is negative

    //Based on that

    public static int getIndexIdentical(int[] a,int low,int high)
    {
    if(a==null || a.length==0)
    return -1;
    int mid;
    if(low<=high)
    {
    mid=(low+high)/2;
    if(mid-a[mid]==0)
    return mid;
    else if(mid-a[mid]>0)
    return getIndexIdentical(a,mid+1,high);
    else
    return getIndexIdentical(a,low,mid+1);
    }
    return -1;
    }

    ReplyDelete
  22. In the Else part its is
    return getIndexIdentical(a,low,mid-1);

    ReplyDelete
  23. It's very useful blog post with informative and insightful content and i had good experience with this information. We, at the CRS info solutions ,help candidates in acquiring certificates, master interview questions, and prepare brilliant resumes.Find top Salesforce admin interview questions in 2020.
    These Salesforce developer interview questions are highly helpful in 2020. You can read these Salesforce lightning interview questions and Salesforce integration interview questions which are prepared by industry experts.

    ReplyDelete
  24. Certain genetic abnormalities affect the function of monocytes élevés and macrophages.

    ReplyDelete
  25. Nice Blog. Thanks for sharing with us. Such amazing information.

    Best MBA College in Dehradun

    ReplyDelete
  26. NAGAQQ: AGEN BANDARQ BANDARQ ONLINE ADUQ ONLINE DOMINOQQ TERBAIK

    Yang Merupakan Agen Bandarq, Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

    Bonus yang diberikan NagaQQ :
    * Bonus rollingan 0.5%,setiap senin di bagikannya
    * Bonus Refferal 10% + 10%,seumur hidup
    * Bonus Jackpot, yang dapat anda dapatkan dengan mudah
    * Minimal Depo 15.000
    * Minimal WD 20.000
    * Deposit via Pulsa TELKOMSEL
    * 6 JENIS BANK ( BCA , BNI, BRI , MANDIRI , CIMB , DANAMON )

    Memegang Gelar atau title sebagai AGEN POKER ONLINE Terbaik di masanya

    Games Yang di Hadirkan NagaQQ :
    * Poker Online
    * BandarQ
    * Domino99
    * Bandar Poker
    * Bandar66
    * Sakong
    * Capsa Susun
    * AduQ
    * Perang Bacarrat (New Game)


    Info Lebih lanjut Kunjungi :
    Website : NAGAQQ
    Facebook : NagaQQ official
    WHATSAPP : +855977509035
    Line : Cs_nagaQQ
    TELEGRAM :+855967014811

    BACA JUGA BLOGSPORT KAMI YANG LAIN:
    Winner NagaQQ
    Daftar NagaQQ
    nagaqq
    berita viral

    ReplyDelete
  27. How Do I Install HP Printer Assistant on My PC?

    The HP printer assistant is software that allows you to print, scan, and all sorts of printer’s functionality. However, if you don’t possess the software, you can download it from the official website of HP and install it by following a few prompts. You may be asked to agree to the terms and conditions. Once you install the tool, double-click on the software icon from the Desktop tray and start printing.

    Also Read:
    Blue Screen on HP Printer
    How to Connect HP Wireless Printer
    HP Printer not Printing Colors Correctly
    Canon mx922 Error b200
    Canon g2000 Error 5200




    ReplyDelete
  28. Get this exclusive dog waterproof suit with legs to save them from all the external factor and let them enjoy the life fullsize with high performance. At Neopaws, we are one of the top online platform for dogs accessories now!

    ReplyDelete
  29. ProFist™ – AV Fistula Needle
    AV Fistula Needle allows venous and arterial access for patients undergoing hemodialysis.
    Ultra-thin wall stainless steel needle (with or without back-eye) siliconized on both internal and external surfaces.
    Provides optimum penetration profile.
    Minimizes pain during insertion , Maximizes smooth, laminar flow
    USP Class VI soft, kink-resistant tubing made from medical-grade PVC.
    Rotating, color-coded wings facilitate flipping of needle while allowing for easy gripping and fixation.
    Orientation dot on needle hub enables precise maneuvering of bevel.
    Luer has universal 6% taper to allow smooth connection with standard bloodline sets.
    Available in single pack or twin-pack for better use of space.
    Available “with” or “without” Back-Eye needle.
    Available with Red, Blue or White Clamp.
    Available with 15 cm or 30 cm Tubing.
    Sizes : 15 G, 16 G & 17 G.
    Individually sterile & blister packed.
    Packing : 50/1000 pcs per Inner /Master carton.
    Master carton dimension : 67×44×28 cm.
    WWW.Lars Medicare.com

    ReplyDelete
  30. While there are as many different possible interview questions as there are interviewers, it always helps to be ready for anything. Which is why we've taken the time to prepare this list of 100 potential interview questions

    ReplyDelete