Count pairs in list of integers such that their addition is equal to the input value
$begingroup$
Given a List<int>
, the problem I am trying to solve is:
Find the number of unique pairs in List<int>
such that their addition is exactly equal to the input value.
The bottleneck is a nested for()
loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int>
of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For()
I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
New contributor
$endgroup$
add a comment |
$begingroup$
Given a List<int>
, the problem I am trying to solve is:
Find the number of unique pairs in List<int>
such that their addition is exactly equal to the input value.
The bottleneck is a nested for()
loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int>
of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For()
I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
New contributor
$endgroup$
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1
and the input value is2
, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago
add a comment |
$begingroup$
Given a List<int>
, the problem I am trying to solve is:
Find the number of unique pairs in List<int>
such that their addition is exactly equal to the input value.
The bottleneck is a nested for()
loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int>
of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For()
I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
New contributor
$endgroup$
Given a List<int>
, the problem I am trying to solve is:
Find the number of unique pairs in List<int>
such that their addition is exactly equal to the input value.
The bottleneck is a nested for()
loop that I have used to go through the list
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int>
of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For()
I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.
Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});
How can I speed this up?
Full code from my console application is as below:
class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;
compareList.Clear();
int nCombinations = 0;
// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}
return nCombinations;
}
// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
compareList.Add(v1 * 10 + v2);
compareList.Add(v2 * 10 + v1);
}
return true;
}
static void Main(string args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;
List<int> intList = new List<int>();
Random r = new Random();
for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}
Stopwatch sw = new Stopwatch();
sw.Start();
// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);
sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}
c# performance k-sum
c# performance k-sum
New contributor
New contributor
edited 4 hours ago
200_success
129k15153415
129k15153415
New contributor
asked 4 hours ago
silverspoonsilverspoon
1061
1061
New contributor
New contributor
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1
and the input value is2
, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago
add a comment |
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is1, 1, 1
and the input value is2
, do we have zero, one or three unique pairs?
$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago
1
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1
and the input value is 2
, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1
and the input value is 2
, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique
doesn't look correct; it is prone to false positives).
There are few standard ways to bring the complexity down.
Sort the list. Arrange two iterators, one at the beginning, another at the end.
Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.
If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.
$endgroup$
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212818%2fcount-pairs-in-list-of-integers-such-that-their-addition-is-equal-to-the-input-v%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique
doesn't look correct; it is prone to false positives).
There are few standard ways to bring the complexity down.
Sort the list. Arrange two iterators, one at the beginning, another at the end.
Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.
If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.
$endgroup$
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
add a comment |
$begingroup$
The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique
doesn't look correct; it is prone to false positives).
There are few standard ways to bring the complexity down.
Sort the list. Arrange two iterators, one at the beginning, another at the end.
Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.
If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.
$endgroup$
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
add a comment |
$begingroup$
The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique
doesn't look correct; it is prone to false positives).
There are few standard ways to bring the complexity down.
Sort the list. Arrange two iterators, one at the beginning, another at the end.
Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.
If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.
$endgroup$
The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique
doesn't look correct; it is prone to false positives).
There are few standard ways to bring the complexity down.
Sort the list. Arrange two iterators, one at the beginning, another at the end.
Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.
If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.
answered 3 hours ago
vnpvnp
39.3k13099
39.3k13099
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
add a comment |
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
$begingroup$
The set approach won't detect 1+1=2
$endgroup$
– Oh My Goodness
3 hours ago
add a comment |
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
silverspoon is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212818%2fcount-pairs-in-list-of-integers-such-that-their-addition-is-equal-to-the-input-v%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is
1, 1, 1
and the input value is2
, do we have zero, one or three unique pairs?$endgroup$
– Oh My Goodness
4 hours ago
$begingroup$
@OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.
$endgroup$
– silverspoon
4 hours ago