Mixing
what can be optimal solution for problem? [duplicate]
This question already has an answer here:
Find 2 numbers in an unsorted array equal to a given sum
18 answers
Let there be an array: [6,9,2,4,1]
I need to find if input number have a pair or not.
Ex. Input - 7
Output - Yes (6+1 )
Input - 16
Output - No (no pair addition is 16)
I know the obvious way by running 2 loops but it have time complexity n^2 . Can someone help me with some optimized solutions ?
Programming Language : Java
What I tried :
1) Sort array
2) Based on input number divide it into 2 subarray (input/2).
3) Inner loop on first array and outer loop on second
This reduces iterations.
algorithm sorting
asked Nov 21 '18 at 12:52
user3857802user3857802
216
marked as duplicate by Paul, jpp, Marvin, Community♦ Nov 22 '18 at 5:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
Find 2 numbers in an unsorted array equal to a given sum
18 answers
Let there be an array: [6,9,2,4,1]
I need to find if input number have a pair or not.
Ex. Input - 7
Output - Yes (6+1 )
Input - 16
Output - No (no pair addition is 16)
I know the obvious way by running 2 loops but it have time complexity n^2 . Can someone help me with some optimized solutions ?
Programming Language : Java
What I tried :
1) Sort array
2) Based on input number divide it into 2 subarray (input/2).
3) Inner loop on first array and outer loop on second
This reduces iterations.
algorithm sorting
asked Nov 21 '18 at 12:52
user3857802user3857802
216
marked as duplicate by Paul, jpp, Marvin, Community♦ Nov 22 '18 at 5:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
1
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc:array.Containsneeds to lookup the data which includes looping through it...
– Markus Safar
Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30
add a comment |
This question already has an answer here:
Find 2 numbers in an unsorted array equal to a given sum
18 answers
Let there be an array: [6,9,2,4,1]
I need to find if input number have a pair or not.
Ex. Input - 7
Output - Yes (6+1 )
Input - 16
Output - No (no pair addition is 16)
I know the obvious way by running 2 loops but it have time complexity n^2 . Can someone help me with some optimized solutions ?
Programming Language : Java
What I tried :
1) Sort array
2) Based on input number divide it into 2 subarray (input/2).
3) Inner loop on first array and outer loop on second
This reduces iterations.
algorithm sorting
asked Nov 21 '18 at 12:52
user3857802user3857802
216
This question already has an answer here:
Find 2 numbers in an unsorted array equal to a given sum
18 answers
Let there be an array: [6,9,2,4,1]
I need to find if input number have a pair or not.
Ex. Input - 7
Output - Yes (6+1 )
Input - 16
Output - No (no pair addition is 16)
I know the obvious way by running 2 loops but it have time complexity n^2 . Can someone help me with some optimized solutions ?
Programming Language : Java
What I tried :
1) Sort array
2) Based on input number divide it into 2 subarray (input/2).
3) Inner loop on first array and outer loop on second
This reduces iterations.
This question already has an answer here:
Find 2 numbers in an unsorted array equal to a given sum
18 answers
algorithm sorting
algorithm sorting
asked Nov 21 '18 at 12:52
user3857802user3857802
216
asked Nov 21 '18 at 12:52
user3857802user3857802
216
edited Nov 21 '18 at 13:14
user3857802
asked Nov 21 '18 at 12:52
user3857802user3857802
216
asked Nov 21 '18 at 12:52
user3857802user3857802
216
asked Nov 21 '18 at 12:52
user3857802user3857802
216
216
marked as duplicate by Paul, jpp, Marvin, Community♦ Nov 22 '18 at 5:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Paul, jpp, Marvin, Community♦ Nov 22 '18 at 5:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
1
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc:array.Containsneeds to lookup the data which includes looping through it...
– Markus Safar
Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30
add a comment |
1
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
1
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc:array.Containsneeds to lookup the data which includes looping through it...
– Markus Safar
Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30
1
1
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
1
1
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc:
array.Contains needs to lookup the data which includes looping through it...– Markus Safar
Nov 21 '18 at 13:04
@Luc:
array.Contains needs to lookup the data which includes looping through it...– Markus Safar
Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30
add a comment |
2 Answers
2
active
oldest
votes
Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:
- Sort your array
- Set up two pointers
lon the leftmost element andron the rightmost - Move the pointers inwards one at a time, using something like the while-loop below:
As follows (pseudocode):
l = 0
r = length(Input) - 1
while l < r:
if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
else if (arr[l] + arr[r] < Input) l = l+1
else r = r-1
return NULL
The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
add a comment |
Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:
1) Create a Hashed Set of the array
2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.
Example:
values = set(array)
for i in array:
if 7 - i in values:
return i, 7-i
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:
- Sort your array
- Set up two pointers
lon the leftmost element andron the rightmost - Move the pointers inwards one at a time, using something like the while-loop below:
As follows (pseudocode):
l = 0
r = length(Input) - 1
while l < r:
if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
else if (arr[l] + arr[r] < Input) l = l+1
else r = r-1
return NULL
The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
add a comment |
Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:
- Sort your array
- Set up two pointers
lon the leftmost element andron the rightmost - Move the pointers inwards one at a time, using something like the while-loop below:
As follows (pseudocode):
l = 0
r = length(Input) - 1
while l < r:
if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
else if (arr[l] + arr[r] < Input) l = l+1
else r = r-1
return NULL
The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
add a comment |
Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:
- Sort your array
- Set up two pointers
lon the leftmost element andron the rightmost - Move the pointers inwards one at a time, using something like the while-loop below:
As follows (pseudocode):
l = 0
r = length(Input) - 1
while l < r:
if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
else if (arr[l] + arr[r] < Input) l = l+1
else r = r-1
return NULL
The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:
- Sort your array
- Set up two pointers
lon the leftmost element andron the rightmost - Move the pointers inwards one at a time, using something like the while-loop below:
As follows (pseudocode):
l = 0
r = length(Input) - 1
while l < r:
if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
else if (arr[l] + arr[r] < Input) l = l+1
else r = r-1
return NULL
The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
edited Nov 21 '18 at 13:10
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
answered Nov 21 '18 at 13:05
BerthurBerthur
709212
709212
add a comment |
add a comment |
Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:
1) Create a Hashed Set of the array
2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.
Example:
values = set(array)
for i in array:
if 7 - i in values:
return i, 7-i
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
add a comment |
Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:
1) Create a Hashed Set of the array
2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.
Example:
values = set(array)
for i in array:
if 7 - i in values:
return i, 7-i
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
add a comment |
Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:
1) Create a Hashed Set of the array
2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.
Example:
values = set(array)
for i in array:
if 7 - i in values:
return i, 7-i
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:
1) Create a Hashed Set of the array
2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.
Example:
values = set(array)
for i in array:
if 7 - i in values:
return i, 7-i
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
answered Nov 22 '18 at 0:13
Ahmed El GoharyAhmed El Gohary
263
263
add a comment |
add a comment |
1
You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } }
– Luc
Nov 21 '18 at 12:54
1
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa.
– vivek_23
Nov 21 '18 at 12:57
@Luc that's still O(n^2)
– Berthur
Nov 21 '18 at 12:57
@Luc:
array.Containsneeds to lookup the data which includes looping through it...– Markus Safar
Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No"
– crazy_coder
Nov 22 '18 at 1:30