arunkumar267
BAN USERThis could be done by modifying the edit distance problem slightly.So After calculating edit distance value return true if it is one else return false.
- arunkumar267 April 23, 2014An O(n^2) solution.
1)Find the sum of elements of entire array
2)Based on the given assumption now find the subset of elements which add upto sum/2.
3)print the elements that are in subset as 1st half and print the elements that are not as 2nd half.
There is a dynamic programming algorithm for finding the subset in O(n^2) time.So the time complexity could be O(n^2).
Another way is to use backtracking which would be O(2^n)
@srikantaggarwal- it returns 1
- arunkumar267 December 31, 2013@srikantaggarwwal No it will work for all cases.You can check
- arunkumar267 December 30, 2013A solution with O(n) time complexity and O(1) space complexity.
Logic:1) maintain 4 variables called count and element element,max count,max element.Initialise count to 1 and maximum element to 1st element of array.
2) while traversing if the element is same as maximum count then increment count by one.
3)Else decrement count.If count reaches zero then assign maximum element to the element at which count became zero and reinitialise the variables
#include<stdio.h>
#include<stdlib.h>
int findMaximumRepeatingElement(int *a,int n)
{
int count=1,maxcount=1,maxelement=a[0];
int element=a[0];
int i=1;
while(i<n)
{
if(a[i]==element)
{
count++;
if(count>maxcount)
{
maxcount=count;
maxelement=a[i];
}
}
else
{
element=a[i];
count=1;
}
i++;
}
return maxelement;
}
int main()
{
int a[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,3,4,4,4,4,4,4,4,5};
printf("%d",findMaximumRepeatingElement(a,sizeof(a)/sizeof(int)));
}
The logic is fairly simple assuming that the number is stored in an array.So once the number is stored in an array we can modify the bubble sort to run the outer loop only for k times.At the end of the loop,the k largest numbers will be at the end in their appropriate position(see working of bubble sort) After this you can reverse the contents of array to get the maximum possible integer.
- arunkumar267 October 03, 2014