@ Gaurav
I don't think the above nlogn approach will work. If i m not wrong,
the above nlogn approach is a modification of the nlogn algo for
maximum continuous subset problem.
I have a doubt with the crossing subarray solution. I see that your if
and while loop breaks out if totalsum =K is not
My implementation, can anyone offer my test cases that i can verify?
struct Deal
{
unsigned int nStartIndex;
unsigned int nEndIndex;
unsigned int nSum;
Deal()
{
nStartIndex = 0;
nEndIndex = 0;
nSum = 0;
}
};
int findBestDeal( const
@ giridhar IS
assuming u wanted k=13 ( max sum =13)
start : i,j points to 1st element
keep a track of sum between i to j
outer loop: till ja.length
sum=sum+a[j]
inner loop till sum exceeds k.
increment i .
@ giridhar IS correction missed increment j in outer loop: sry :-)
assuming u wanted k=13 ( max sum =13)
start : i,j points to 1st element
keep a track of sum between i to j
outer loop: till ja.length
sum=sum+a[j]
increment j
inner loop
@ sourabh :-) yep, got your point... it wont work for all cases.
but
if we set initial max to a negative value . say max possible 64 bit
-ve number.then ?
point is though the code has limitations it will work fine mostly.
On 12/5/11, sourabh sourabhd2...@gmail.com wrote:
@sourabh singh..
Hey
@sourabh
can you explain me how it will work for this example
a[]={2,7,3,4,5,8,10}
On Dec 7, 12:17 am, sourabh singh singhsourab...@gmail.com wrote:
@ sourabh :-) yep, got your point... it wont work for all cases.
but
if we set initial max to a negative value . say max possible 64 bit
@sourabh..
I don't think it will work for all the cases.. did u consider negative
integers as well... what i can understand from the above code is that
u have taken 2 pointers of which one points to the beginning of the
subarray and other one at the end of the subarray and u r shifting the
@ sourabh tried some cases its working on -ve as well. pls post some
case in which it might not work.
On 12/5/11, sourabh sourabhd2...@gmail.com wrote:
@sourabh..
I don't think it will work for all the cases.. did u consider negative
integers as well... what i can understand from the above
@sourabh
i guess you need to modify this statement :-
3) Now for each element B[i][0] , do a (modified) binary *search for
the closest value smaller than equal to (X + B[i][0])* in array B[i
+1... n][0] ,
Say the found index after binary search is j ( which is i)...
12 + 2 = 12 , closest
and you made mistake above in calculating 12 + 2 = *12* , its 14
12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 , i
= 1, j = 4
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i
= 2, j = 4
12 + 6 = 18 , closest element found = 15 , closest to X = 15
@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
i = 3, j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
=5 , i = 4, j = 4
yup i made some calculation error
Now this algo works perfectly :) :)
Thanks for your help and explanation :) :)
On Thu, Dec 1, 2011 at 4:26 PM, sourabh sourabhd2...@gmail.com wrote:
@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 =
@atul...
thanks dude for ur thorough screening of the algo and pointing out the
mistakes... I think that's y its always said that until and unless we
don't turn an algo to a working code we are never really sure whether
its perfect and covers all the cases.
On Dec 1, 4:23 pm, atul anand
A little variation of kadane's algo will do as written below: -
#include stdafx.h
#include stdlib.h
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = {-1,3,1,2,-3};
int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0 ,
endIndex = 0, itr = 0;
int k=12;
@ankit : sorry dude , its not working for given input
{2,1,3,4,5} k=12,
ans=12, sub-array={3,4,5}
your algo will give ans=10 sub-array{0 to 3}
On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha akki12...@gmail.com wrote:
A little variation of kadane's algo will do as written below: -
#include
@ankit...
I don't think the algorithm is correct...
The check max_ending_here 0 max_limit_here =k doesn't look
correct...
Also I am not able to figure out the importance of 0 in the check ..
Ankit, may be I am wrong. Hence, can you come up with the algorithm
explaining ( with a set of steps )
Given array of integers A[n],
create an array B[n] such that B[i] = sum of all elements from A[1]
to A[i],
Now sort array B, and for each element B[i] ( smaller that equal to
X), do a (modified) binary search for the closest value smaller than
equal to (X - B[i]) in array B[i+1... n]
Keep
Given array of integers A, create an 2-d array B of size n*2 such
that B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
sort array B based on B[i][0]..
Now for each element B[i][0] ( till its smaller that equal to X), do a
(modified) binary search for the closest value smaller
@sourabh : please let me know where i am making mistake in understanding
your algo:-
considering your 1st algo:-
1) Given array of integers A[n], = {2,1,3,4,5}
2) create an array B[n] such that B[i] = sum of all elements from A[1]
to A[i], // i guess it should be A[0] to A[i]
Array B formed
First i would like to rectify a editing mistake that is as foolws :
Say the found index after binary search is j ( which is i)..
Now if B[i][1] B[j][1] then keep track of the max no. closest to X
( that is B[i][0] + B[j][0])... // earlier the last text was B[i][1] +
B[j][1]
Now to clarify your
I am rewriting the algo here in much more readable form :
Given array of integers A,
1) Create an 2-d array B[n][2] of size n*2 such that
a) B[i][0] = sum of all elements from A[0] to A[i],
b) B[i][1] = i
2) Sort array B based on B[i][0] i.e. sort array B[][0] and
correspondingly
@sourabh :
*Cumulative SUM*
*i*
2
0
3
1
6
2
10
3
15
4
above will the array B[][] formed for array A[]={ 2,1,3,4,5 }
let X=12;
12 - 2 = 10 , closest element found = 10 , *closest to X = 2 + 10 =12*
,*i = 0 , j = 3
* // this is the answer , so i am calculating other
max
@atul.. thanks for pointing out.. i m doing a small mistake in
calculating closest element found... and i have rectified it below...
Also i have missed a corner case in the above solution hence i m
putting it down here...
3a) Corner case: Do modified binary search for closest element smaller
than
@Gene - nice, correct and elegant algorithm.
On Wed, Nov 23, 2011 at 9:33 PM, Ankur Garg ankurga...@gmail.com wrote:
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On
@Gene : Are you sure, when you pop element from stack it will not be next
smaller element to remaining elements in the array(Input)?? I think this is
not gonna work...
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also
Here is my code with logic techcoder described ...
void PushSmallerElement(int a[],int n){
stackpairint,int s;
pairint,intp;
int top;
for(int i=0;in;i++){
if(s.empty())
s.push(pairint,int(a[i],i));
else{
p=s.top();
while( !s.empty() a[i]p.first ){
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a,
It's a variation of next greater element problem (
http://www.geeksforgeeks.org/archives/8405). Instead of next greater
element, this problem asks about next smaller element.
On Wed, Nov 23, 2011 at 5:29 PM, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov
One way could be sorting the array and also storing the original index
along with that. After that we can search linearly in the array.
On Nov 23, 5:40 am, Anup Ghatage ghat...@gmail.com wrote:
What do you mean by if this number is less than elements stored in
stack
There have be N
Can we replace the operator (/) with 1^(-n) ?
On Sep 30, 12:54 pm, raju nikutel...@gmail.com wrote:
@nitin ..
Output array is not a new array ... you can do anything to input array ..
~raju
On Fri, Sep 30, 2011 at 1:24 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
Can we assume
int main()
{
int a[]={4,3,5,2,6}; // 1 4 12 60 120
const int n=5;
int temp=1,i;
int b[5]={0};
for(i=0;in;i++)
{
b[i]=temp;
temp*=a[i];
}
temp=1;
for(i=n-1;i=0;i--)
{
b[i]*=temp;
temp*=a[i];
@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers getting 7 = 111 in binary. Now
how do we divide the numbers into two groups?
Dave
On Aug 26, 11:09 am, tech coder
I believe this is what techcoder is saying:
int a[N];
// Find the bitwise xor of all the array values.
// These are the bits which are different between the two results.
int xor = 0;
for(i = 0; i N; ++i)
xor ^= a[N];
// Find the low order bit of xor
int bit = 1;
while(!(xor bit))
bit = 1;
XOR all the elements in the array, the result will be the XOR of the two
numbers occuring odd number of times.
Now take any set bit of th result(u can determine the position of any bit
set in the number). Divide the array such that for the numbers for which at
this location(where the bit is set
@Tech, Don: How about this: given n and array a[n]:
int x = 0, result[2] = {0};
for( i = 0 ; i n ; ++i )
x ^= a[i];
x |= x(x-1); // low order 1-bit of xor
for( i = 0 ; i n ; ++i )
result[a[i]x?0:1] ^= a[i];
Dave
On Aug 26, 12:49 pm, Don dondod...@gmail.com wrote:
I believe this is
@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers getting 7 = 111 in binary. Now
how do we divide the numbers into two groups?
see we come to know that both number differ at
@ Don exactly waht u write i wanted to say
On Fri, Aug 26, 2011 at 11:52 AM, tech coder techcoderonw...@gmail.comwrote:
@Tech: I'm not sure I understand your algorithm. Let's try it on
{1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
times are 3 and 4. We xor the numbers
@don really cool algo man
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
@Sachin: You can sort the array in O(n log n), and then finding the
two numbers is an additional O(n), so the resulting complexity is O(n
log n).
Dave
On Aug 25, 2:01 pm, sachin sabbarwal algowithsac...@gmail.com wrote:
We have an array which contains integer numbers (not any fixed range). Only
43 matches
Mail list logo
