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

frogInSea

 Profile Answers by frogInSea Questions by frogInSea

• Mar 14th, 2013

I think it can be solved in a two dimensional Binary-Search way

Answer Question  Select Best Answer

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?

cullensun

 Profile Answers by cullensun Questions by cullensun

• Sep 23rd, 2013

1st, 2nd, 3rd,......, (n-1)th, (n)th, (n+1)th, (n+2)th, ...... (2n)th Focus: Identify the the repeated element 1. take the 1st element to compare with the rest one by one, worst case: compare wi...

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)

Answer Question  Select Best Answer

Give an algorithm that calculates the distance between two text strings (only operations you can have are: delete, add, and change, one by one).

rrc_83

 Profile Answers by rrc_83 Questions by rrc_83

• Jun 20th, 2010

In python - # Input is string s1 and string s2# Check which string is bigger (compares ascii value)if s1 > s2:  b, s = s1, s2else :  b, s  = s2, s1# Covert string to listl1, l2 = lis...

yzesong

 Profile Answers by yzesong Questions by yzesong

• Aug 9th, 2009

The distance of two strings, like "car" and "cat", is 1. So all we need to do is, compare two strings one character by one character and get the distance value. The complexity is O(max(m,n)), m, n are the length of each string.

Answer Question  Select Best Answer

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!

Gaurav.khurana

 Profile Answers by Gaurav.khurana Questions by Gaurav.khurana

• Apr 25th, 2015

@vandita Just a minor correction i think we should go till n-1 only so the in for loop it should be and should use i+1 since nbrs are starting from 1 and not 0

Code
for (int i=0 ; i<n ; i++)
{
  swap(a[i],a[a[i]-1]
}
//since 1 is stored at 0th position

bakesh

• Mar 16th, 2015

9

Improve Answer