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. One of the ways to do this is using some Offset, so the number A will be A + Offset.
On 22 окт, 20:49, Mridul Malpani <[email protected]> wrote: > 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++" <[email protected]> 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, 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; // found solution > > > } > > > // check pointers > > if (l != r) then you found solution, so A[l] + A[r] == m > > > On 22 ÏËÔ, 15:32, RIDER <[email protected]> wrote: > > > > you have an array of n integers, how would you find the integer pairs > > > which sum to m? complexity? > > > > if we use hash table then should we implement efficient hash table in c > > > ++? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
