PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

2nd smallest number from 32 numbers

(5 votes, average: 4.40 out of 5)

May 27, 2014 by puzzler 20 Comments

You have 32 numbers. What is the least number of comparison needed to find the 2nd smallest out of them?


Check your answer:-

Tried enough already?
Click here to See AnswersHide Answer
Minimum number of comparisons required will be n + log(n) -2 = 32 + 5 -2 = 35
How?
We can think of this as a tournament where 32 teams are competing against each other, to get the best team out of n teams we need (n-1) comparisons, by taking two teams at a time and then playing the game between the previous winners, Games will be played in the tree format as below

             |
         |       |
       |   |   |    |
      | | | | | |  | |

Now we need to find the second best team: We can say that second best team must have lost against the winner(as otherwise it will not be second). And Total number of games played by the winner are log(n) (height of the tree).
Now our task reduces to just finding the best team from log(n) teams, which we know can be done in log(n) – 1 times.

So total number of comparisons = n-1 + log(n) -1 = n + log(n) -2.

Solution reference: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
Three blue and two red hats puzzle

Checkout more Interview Questions Tags: Snapdeal Interview Questions, Solved Puzzles

Comments

  1. Baballa says

    September 21, 2016 at 10:28 am

    32 “SORTED” numbers.

    Reply
  2. steven k says

    September 22, 2015 at 12:59 pm

    Inter change the elements in the array and do 31 iterations to identify the second largest. Using sorting techniques, time complexity goes beyond n. i.e, 32.

    Reply
  3. jjjjj says

    June 19, 2015 at 9:15 am

    jjjjjj

    Reply
  4. Gopal Zawar says

    May 5, 2015 at 3:20 am

    47

    Reply
  5. Praveen Benny says

    January 9, 2015 at 7:22 pm

    61

    Reply
  6. Priyamyolo says

    November 11, 2014 at 9:26 pm

    It’s just 35

    Reply
  7. Ganesh says

    August 20, 2014 at 9:31 am

    pls find the revised solution

    int SecondMin = 0;
    int Min = 0;

    if(arr[0] > arr[1])
    {
    SecondMin = arr[0];
    Min = arr[1];
    }

    else
    {
    SecondMin = arr[1];
    Min = arr[0];
    }

    for(int i = 2 ; i < arr.Length -1 ; i++)
    {
    if ( arr[i] < Min )
    {
    SecondMin = Min;
    Min = arr[i];
    }
    else if(arr[i] < SecondMin)
    {
    SecondMin = arr[i];
    }
    }

    it will work in O( N -1 )

    Reply
    • puzzlersworld says

      August 20, 2014 at 3:58 pm

      We wanted total comparisons done, here we are doing way more than 35..(look for all comparisons)

      Reply
    • Sup says

      July 20, 2016 at 11:20 am

      Hey Ganesh just check the nunber of times the if and else if conditions r being checked… Its 2(n-1).

      Reply
  8. Ganesh says

    August 20, 2014 at 9:19 am

    How about this ?

    Imagine arr[] is the array of elements

    int SecondMin = arr[0];
    int Min = arr[0];

    for(int i = 1 ; i < arr.Length ; i++)
    {
    if ( arr[i] < Min )
    {
    SecondMin = Min;
    Min = arr[i];
    }
    }

    so in the end of the loop i will get my second minimum in 31 comparisons.

    Reply
    • puzzlersworld says

      August 20, 2014 at 9:26 am

      There is a boundary case where this will not work(first number is minimum of all)
      lets assume the array is
      1,2,3,4,5,6,7,8

      Now what will your code return as second min ?

      Reply
  9. manish says

    August 12, 2014 at 6:27 am

    16

    8

    4

    2

    1
    So the total is 31… and thats the answer

    Reply
    • Dimitris Kaka says

      November 11, 2015 at 7:00 am

      We want the second smallest number between 32 numbers. 31 is the correct answer for the Smallest number. In this problem, the right solution is 35.

      Reply
  10. Mukesh Kumar says

    July 1, 2014 at 4:04 pm

    it must be 31.
    we can go through divide and conquer and when we have two numbers we find the maximum of them
    so the answer will be 31.

    Reply
    • puzzlersworld says

      July 15, 2014 at 9:05 am

      its for second highest number, not the first one

      Reply
      • Riya says

        January 3, 2015 at 9:10 pm

        Even for the binary tree type structure , we need a total of 16+8+4+2+1=31 comparisons , to find the maximum number , once we find that we know the second largest number , so correct answer should b 31 🙂

        Reply
        • puzzlersworld says

          March 9, 2015 at 9:37 am

          no, lets say out of 16 comparisons, first comparison was among the first and second highest, in that case second highest will not come in next 8 numbers and thus it is not compulsory that the last 2 numbers are first and second highest.

          Reply
        • Omer Farooq says

          August 26, 2015 at 11:39 pm

          35

          Reply
      • Deepak Maurya says

        July 27, 2016 at 5:10 pm

        one who loose against the winner is the second winner so no more comparison needed.
        To get the winner we are getting 31 comparison same for looser in the final round(2nd winner)

        Reply
  11. livinggod29.com says

    May 27, 2014 at 6:38 pm

    32 should be the answer

    Reply

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Swap two integer variables
  • Minesweeper Master Solution – Google Code jam 2014
  • Rotate an array by k elements
  • Average speed of train
  • Basic Concepts C/C++
  • Manage Your Energey Solution: Google codejam 2013 Round 1A
  • Card Game solution: Facebook hacker cup 2013 Round1
  • Find the Min solution: Facebook hacker Cup 2013 Qual Round
  • Full Binary Tree Solution – Google Code Jam
  • Cake Cutting solution: Facebook hacker cup 2013 Round 2

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2023 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    â–¼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    â–²
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous