fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. namespace mj {
  6. void merge(int *A, int *B, int *mapA, int *mapB, int *MA, int M, int N)
  7. {
  8. 	int i = 0, j = 0;
  9. 	while(i < M && j < N) {
  10. 	    if(A[i] < B[j]) {
  11. 	        MA[i+j] = A[i];
  12. 	        mapA[i+j] = i;
  13. 	        i++;
  14. 	    } else {
  15. 	        MA[i+j] = B[j];
  16. 	        mapB[i+j] = j;
  17. 	        j++;
  18. 	    }
  19. 	}
  20. 	while(i < M) {
  21. 	    MA[i+j] = A[i];
  22. 	    mapA[i+j] = i;
  23. 	    i++;
  24. 	}
  25. 	while(j < N) {
  26. 	    MA[i+j] = B[j];
  27. 	    mapB[i+j] = j;
  28. 	    j++;
  29. 	}
  30. }
  31.  
  32. void search(int *mapA, int *mapB, int *MA, int M, int N, int answer)
  33. {
  34. 	int i = 0;
  35. 	int j = N + M - 1;
  36. 	while(i < j){
  37. 	   if(mapA[i] == -1) i++;
  38. 	   else if(mapB[j] == -1) j--;
  39. 	   else if (MA[i] + MA[j] == answer) {
  40. 	   		cout << "A[" << mapA[i] << "] + B[" << mapB[j] << "] = " << MA[i] << " + " << MA[j] << " = " << answer << endl;
  41. 	   		return;
  42. 	   } else if (MA[i] + MA[j] <  answer) i++;
  43. 	   else if (MA[i] + MA[j] >  answer) j--;
  44. 	}
  45. 	cout << answer << " not found" << endl;
  46. }
  47.  
  48. }
  49.  
  50. int main() {
  51. 	int A[] = {1,2,3,4,5};
  52. 	int B[] = {6, 7, 8, 9, 10}; // Assuming both are sorted
  53. 	const int M = sizeof A / sizeof A[0];
  54. 	const int N = sizeof B / sizeof B[0];
  55. 	int MA[M+N], mapA[M+N], mapB[M+N];
  56.  
  57. 	fill(mapA, mapA + M + N, -1);
  58. 	fill(mapB, mapB + M + N, -1);
  59. 	mj::merge(A, B, mapA, mapB, MA, M, N);
  60.  
  61.     mj::search(mapA, mapB, MA, M, N, 13);
  62.     mj::search(mapA, mapB, MA, M, N, 16);
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
A[2] + B[4] = 3 + 10 = 13
16 not found
https://ideone.com/QLE6Qq
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!