krish
BAN USERI have written the program in C#...see if it works..m not sure about the complexity..may b O(n)
static void Main(string[] args)
{
List<Char> list1 = new List<char>() {'a','c','d','r','e','g','t' };
List<Char> list2 = new List<char>() { 'a', 'c', 'w', 'r', 'e', 'g', 't','f' };
int count = 0, max = 0, final = 0;
if (list1.Count <= list2.Count)
{
count = list1.Count;
for (int i = 0; i < count; i++)
{
if (list1[i] == list2[i])
max++;
else
{
final = max;
max = 0;
}
}
}
final = max;
Console.WriteLine("Final: {0}", final);
}
I will use divide and conquer approach. I am considering it as an array.
- krish April 09, 2012Lets have two vars, int lower and int min.
int arr[]= {2,4,5,7,10,1,20,14,2}
start with middle element..say at index 4 i.e. arr[4] = 10
now lower would be index of previous element..3
i will go backwards by decreasing value of lower till it becomes 0 and i will subtract each element from arr[4] and will store result in 'min'.
so min = 10-6 = 4,
lower--;
if(10-7)<min then min = 10-7 = 3 and so on.
when lower reaches 0 will increment array index..ie. I will take the current element as arr[5] and repeat the same procedure again..finally i will get min value as minimum difference.
I am not sure about the complexity..can anyone tell me??