Hi all,
Given a 2d array which is sorted row wise and column wise as well,
find a specific element in it in LESS THAN O(n).
PS: an O(n) solution would involve skipping a column or a row each
time from the search and moving accordingly.
Solution less than O(n) is desirable!
--
You received this me
Here is the Simplest working solution :)
bool check(int x[],int y[],int n)
{
c=0;
for(int i=0;iy) != (y[j]>y)) && (x-x[i]/x[j]-x[i] < y-y[i]/y[j]-y[i])
c=!c;
}
return c;
}
On Sep 20, 7:46 pm, umesh kewat wrote:
> Initially we have given three point A , B, C in plane represent three nodes
> of
@Minotauraus: ur approach is flawed!
the BEST solution would be to use a maxheap as navin said! :)
On Sep 21, 1:55 pm, Naveen Agrawal wrote:
> @Minotauraus
>
> Your algo is wrong
> Consider this case:
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
> 99 98 97 96 95 94 93 92
You are given a string which is sorted.. Write a recursive function to
remove the duplicate characters in the string.
eg: potatoeos
output: potaes
NO extraspace like hash/ bitmaps..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to t
Hi Raj,
I think there is an nlogn solution to this problem which can be done
by modifying merge sort..
the key lies in the merge routine, when the left array elements are
greater than the right array,
the right array elements are copied to the tmp array .. hence , this
adds (n-i) to the inversion
Hi,
O(n) solution is possible if the array is presorted!
Else i think it is NOT.
1.Have two ptrs (one from first and other to track the array from
last)
2.s=a[left]+a[right]
3.if(ssum) right--;
else
print "sum found"
On Sep 10, 10:19 pm, bittu wrote:
> Q Given an array, find out if there exis
Hi Bittu,
Your algorithm uses Linear extra space. which is proportional to the
input used.
There is a better algorithm which is linear in time and does alot
better .
int Majoritycount(int [] A) {
int ctr=1;
//counter is a variable to indicate the relative importance of the
element. as successive
Further more you are not printing the factorial itself!
On Sep 4, 7:02 pm, jagadish wrote:
> @Nuan:
> Hi Nuan,
>
> The problem states that
>
> "An integer t, 1<=t<=100, denoting the number of testcases, followed
> by t lines, each containing a single integer n,
@Nuan:
Hi Nuan,
The problem states that
"An integer t, 1<=t<=100, denoting the number of testcases, followed
by t lines, each containing a single integer n, 1<=n<=100."
N lies between 1 to 100..
Such a naive approach like yours would fail for larger numbers!
That is why you are getting a wrong
HI Arun,
This is the edit distance problem which can be solved using DP.
Calculate the cost for each product on the fly and return the top
products with the least edit cost!
On Sep 1, 5:15 pm, Arun wrote:
> You are given the amazon.com database which consists of names of
> millions of products.
@Dave: Thanks alot for enlightening us!
@Manju: ya.. you are right. The same was stated by me in the my prev
reply! :-)
On Aug 29, 10:50 pm, Manjunath Manohar
wrote:
> it is compiler dependant da..the evaluation of this kind of expressions
--
You received this message because you are subscribe
@Rahul Patil:
I ran your code on some basic test cases and i found it to be
correct!
Can you please explain the logic you used to arrive at the solution?
Thanks :-)
On Aug 29, 12:25 pm, rahul patil
wrote:
> check out this solution.I think this works correct
> will explain logic if u find it c
I think a solution to convert a Binary Tree to a Doubly Linked List
has been discussed!
On Aug 27, 9:32 pm, balashankar sundar wrote:
> head=new node;//head node to list,T is root to the tree
> join=head;//global variable
>
> inorder(T)
> {
> if(T==0)
> return;
> inorder(t->l)
Ya after some reading i got to know that it was implementation
dependent..
And that the answer is undefined!
On Aug 28, 5:07 pm, Chi wrote:
> In php it is 19.
>
> $x=5;
> printf("%d",($x++ + ++$x + $x++));
> ?>
>
> On Aug 28, 1:35 pm, jagadish wrote:
>
I ran this code..
int main() { int x=5;
printf("%d",(x++ + ++x + x++));
}
The output printed was 18 instead of 19.. Should it not be 19?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegr
@Gene:
It would be helpful if you could throw some light on the sub structure
of the problem!
And how to formulate it..
Thanks for your time :)
On Aug 28, 8:36 am, Gene wrote:
> Yes. Exactly. DP will get it.
>
> On Aug 27, 11:34 pm, jagadish wrote:
>
> > Ya it fails..
Should it be done using dynamic programming then?
On Aug 28, 8:32 am, jagadish wrote:
> @Aravind: I think the solution given by Gene works!.
> The answer for 8 2 2 2 2 2.. is six..
>
> On Aug 28, 8:26 am, jagadish wrote:
>
> > @Gene: Thanks alot! :-) your solution works lik
Ya it fails.. Should it then be Dynamic Programming then??
On Aug 28, 8:32 am, jagadish wrote:
> @Aravind: I think the solution given by Gene works!.
> The answer for 8 2 2 2 2 2.. is six..
>
> On Aug 28, 8:26 am, jagadish wrote:
>
> > @Gene: Thanks alot! :-) your solu
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish wrote:
> @Gene: Thanks alot! :-) your solution works like charm!
>
> On Aug 28, 7:09 am, Gene wrote:
>
> > This is a nice problem. It looks like a tri
heaper. Do it.
> total_cost += a[i + 1];
> for (j = i + 1; j < n - 1; j++)
> a[j] = a[j + 1];
> --n;
> }
> }
> }
> return total_cost;
>
> }
>
> int main(void)
> {
> int a[] = { 14, 15, 16, 13, 11, 18 };
>
@Rahul:
Yea that is admissible.. Each decrement will add one to the cost!
On Aug 27, 9:36 pm, Rahul Singal wrote:
> can u decrement d same element more then once ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, sen
You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element
For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3
--
You received this messa
In the general case, we can reduce Element-Distinctness(ED) problem to
this problem. Since ED has a lower bound of Omega(n log n), we cannot
get an O(n) algorithm for this problem.
http://en.wikipedia.org/wiki/Element_distinctness_problem
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
On Jun
>Why not just change the definition of when one number is bigger than another
>and do normal sort ?
>I guess that is better and simpler.
Normal sort takes O(n log n), while Anurag's algo is O(n).
Regards,
Jagadish
http://www.cse.iitb.ac.in/~jagadish
On Jun 20, 2:18 pm, Rohi
standard algorithm for median
finding can be tweaked to use only constant extra space.
@Bharath: It's a nice algorithm, nevertheless :)
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group
> 3) Whenever a number repeats instead of storing the count store modify the
> number to (number + ROOT Value) ie for 2 which is repeated twice 2 + 3 +3 =
> 8 instead of 2:3 as you give in your example.
>
> 4) Since in a heap no number can be greater than root value whenever a
> number greater tha
:23:2
and so on...
Since, there are only k distinct keys the heap size will at most be k;
so each search/insert/increment operation takes O(log k) time.
Jagadish
http://www.cse.iitb.ac.in/~jagadish
>
> On 2010-5-17 22:38, Jagadish M wrote:
>
>
>
> > The best algorithm
On May 17, 5:36 pm, Rohit Saraf wrote:
> @divya : descending order sorting works. BRILLIANT !!
Not really.
Try this input: 8 6 5 5 5 1
The best partition is [8 6 1] [5 5 5] but Divya's algorithm gives [8
5 1] [6 5 5].
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
> On 5/1
The best algorithm I can think of is to maintain a heap of k elements.
Takes O(n log k) time.
Is anything told about the values of the keys? If the keys have values
less than N, then it is possible to do
what you say, i.e sort them in place.
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
On May
>
> > Try dynamic programming. Complexity of the algorithm would be O(n^3).
>
Won't it just be O(n^2)?
Suppose A is the input.
Let F(i,+) denote the maximum sum you can accumulate with the sequence
ending at A[i] and the last difference being positive.
Define F(i,-) accordingly. Computing each F
30 matches
Mail list logo
