@mohit,ruturaj
We dont need to know the range only if there are +ve no's.
and then also we need only m/2 space.
if(a[i]>m)
skip
else
if(a[i]>m/2)
if(hash[m-a[i]]==1))
return true;
else
hash[m-a[i]]++;
else
if(hash[a[i]]==1))
return true;
else
hash[a[i]]+
@bittu : for that array should be short...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
On Nov 14, 10:58 pm, bittu wrote:
> ya much works is done by above candidate.
> i would like to say..use 2 ptrs one from beginning & another from end
> take sum=a[start]+a[end];
> find if sum>num
> end--
> else if sum start++;
> else //sum==num
> found;
>
> time compexcity O(n) sizeof array
>
ya much works is done by above candidate.
i would like to say..use 2 ptrs one from beginning & another from end
take sum=a[start]+a[end];
find if sum>num
end--
else if sumhttp://groups.google.com/group/algogeeks?hl=en.
On Oct 27, 8:21 am, "MOHIT " wrote:
> @ruturaj : but for that hash table you have to know range??
Nope we dont need the range.
#include
map hash;
for(int i=0;i 0)count++;hash[a[i]]++;
does the trick.
--
You received this message because you are subscribed to the Google Groups
"Algorit
To solve this we use a hash table (stl perhaps)
for i=1 to n:
if (hash[m-a[i]] == 1)pair found;
else set has[m-a[i]] = 1;
with this everytime we hit m-x and we have hit x till now we get a
pair.
On Oct 22, 4:32 pm, RIDER wrote:
> you have an array of n integers, how would you find the integer pa
but can anyone answer how should make effective hashtable in C++ ... we
should used STL or any custom made hash function so that we need to search
in O(1)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to al
Oh Yeah. I got it :) Thanks!
On Mon, Oct 25, 2010 at 8:47 AM, mo...@ismu wrote:
> @preethika (3,1) is found while inserting 1 and (2,2) will be found while
> inserting second 2 (which is at last position)
>
> --
> You received this message because you are subscribed to the Google Groups
>
@preethika (3,1) is found while inserting 1 and (2,2) will be found while
inserting second 2 (which is at last position)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To
@Mohit: I still did not get it.
Suppose m = 4
And the integers are 5 3 2 7 1 2 ...
How do you proceed? Here the answer is (3,1) & (2,2).
On Mon, Oct 25, 2010 at 7:04 AM, MOHIT wrote:
> @preethika : .. mohan is right .. better to do it while inserting because
> may be u can get answer wi
@preethika : .. mohan is right .. better to do it while inserting because
may be u can get answer without hashing all element in between
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@goog
@preetika: you are not suppose to find at first insertion but may be you can
find at 2 or 3 rd or may be nt step
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscr
@Mohan - If there are more than one pair of integers that satisfy the
condition, then?
On Mon, Oct 25, 2010 at 8:07 AM, mo...@ismu wrote:
> u check only that element and continue inserting other elements
>
> ex m=4
>
> elements
> 5 3 2 7 1 2 ...
> (3,1) will be found while inseting 1 , not
u check only that element and continue inserting other elements
ex m=4
elements
5 3 2 7 1 2 ...
(3,1) will be found while inseting 1 , not 3
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algog
@Mohan- Suppose we have inserted 1st element, how do we check whether
sum-element exists or not since hashtable consists of only 1 element at this
point of time. Could you please elaborate?
On Mon, Oct 25, 2010 at 7:00 AM, mo...@ismu wrote:
> @preethika bettter to do it while inserting itself..
@preethika bettter to do it while inserting itself
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@goog
@Mohit : Then insert all the elements in hashtable and scan the hashtable in
O(n) time. While scanning each elements, you have to search for
(sum-element) element in the hashtable (O(1) time). What do you think?
On Sun, Oct 24, 2010 at 12:51 PM, MOHIT wrote:
> @preetika : we can use hash ta
@preetika : we can use hash table for O(n) complexity ..if array is not
sorted .. i am looking for that answer... how should i make that hash table
so that searching in hash table become O(1) complexity.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geek
I think we can sort the elements first and then start scanning from both
ends of the array. All the pairs can be found this way and the complexity
will be O(nlogn).
On Sun, Oct 24, 2010 at 6:08 AM, Avik Mitra wrote:
> We can follow an algorithm described below.
>
> Set found:= FALSE
> For each n
We can follow an algorithm described below.
Set found:= FALSE
For each number n belong to array A.and until found != TRUE
For each number k in A not equal to n, do:
if k+n == m then
output "The pairs are n and k"
Set found:=TRUE.
Break.
The running time will be of O(
Iterate over an array and add number to the set (simply set up an
appropriate bit there).
Every time check if there exists in the set number A = m -
currentNumber (check corresponding bit in the bitset).
So the complexity is O(N).
Additional care should be taken for working with negative numbers.
O
if array is not sorted, then how u are solving it in O(n) using
bitset.
will u plz explain??
On Oct 22, 9:15 pm, "juver++" wrote:
> You may use C++ bitset. It requires O(Max / 8) bytes for space.
> If the array is sorted, there is O(n) solution with O(1) space
> complexity:
> keep two pointers, l
You may use C++ bitset. It requires O(Max / 8) bytes for space.
If the array is sorted, there is O(n) solution with O(1) space
complexity:
keep two pointers, left = 0 and right = n - 1;
while (l < r) {
int diff = A[l] + A[r] - m;
if (diff > 0) --r;
else if (A[l] + A[r] < 0) ++l;
else break;
23 matches
Mail list logo