Answered Questions

  • Sorted Matrix

    You are given a matrix. The matrix elements are such that they are sorted both horizontally and vertically. Given an element of the matrix, your job is to obtain its position in an efficient manner.Example: 10 20 30 15 35 98 48 76 110Input: 76Output: 3rd row, 2nd column.

    sandy

    • Mar 24th, 2013

    I assume you can do it in the following way: "python class Coordinate: def __init__(self,x=0,y=0): self.x = x self.y = y def findElement(a,n): if a == Non...

  • Duplicate Elements Array

    You have an array of size '2n' of these, 'n+1' elements are distinct and 1 element is repeated 'n' times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?

    shankar

    • Oct 16th, 2012

    Since an element is repeated more than half the occurance of the array, for every two didtinct elements discard them from the array. At the end of the loop, the most repeated element will be left.

    This is O(n)

  • There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..).

    Star Read Best Answer

    Editorial / Best Answer

    Answered by: David Rachutin

    • Dec 27th, 2006


    use the following method:

    mark the missing number as M and the duplicated as D

    1) compute the sum of regular list of numbers from 1 to N call it RegularSum

    2) compute the sum of your array (the one with M and D) call it MySum

    now you know that MySum-M+D=RegularSum

    this is one equation.

    the second one uses multiplication:

    3) compute the multiplication of numbers of regular list of numbers from 1 to N call it RegularMultiplication

    4) compute the multiplication of numbers of your list  (the one with M and D) call it MyMultiplication

    now you know that MyMultiplication=RegularMultiplication*D/M

    at this point you have two equations with two parameters, solve and rule!

    bakesh

    • Mar 16th, 2015

    9