Skip to main content
Add big-O notation
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10

Here is an alternative approach using set logic, which is O(n) in the average case:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic, which is O(n) in the average case:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

short-circuit case where (n2, n2) in pairs
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {nx for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {n for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

use greater/less than split
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
numset = set(numbers)
goodnums = {n-x for x in numbers if x<=n2} & numset{n for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
numset = set(numbers)
goodnums = {n-x for x in numbers if x<=n2} & numset
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Here is an alternative approach using set logic:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {n for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

Use list.count
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10
Loading
Add explanation
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10
Loading
Source Link
TheBlackCat
  • 2.4k
  • 11
  • 10
Loading