Mixing
Given a set of numbers, is there a quick way to find the two numbers which their product is closest to a...
$begingroup$
Suppose I have a set of triangle numbers A = {1, 3, 6, 10 ...} (2000 items)
I want to find the pair of numbers in AxA (i.e. 1*3, 1*6, 3*6..., a*b,...) where the product a*b is closest to N. (N = 2000000).
What I tried was to generate the pairs of numbers and then get abs(N - a*b) and sort, and find first pair. But I find it too slow.
Is technique I can use here to easily arrive at an answer?
combinatorics
asked Jan 23 at 3:01
nakiyanakiya
1134
$endgroup$
add a comment |
$begingroup$
Suppose I have a set of triangle numbers A = {1, 3, 6, 10 ...} (2000 items)
I want to find the pair of numbers in AxA (i.e. 1*3, 1*6, 3*6..., a*b,...) where the product a*b is closest to N. (N = 2000000).
What I tried was to generate the pairs of numbers and then get abs(N - a*b) and sort, and find first pair. But I find it too slow.
Is technique I can use here to easily arrive at an answer?
combinatorics
asked Jan 23 at 3:01
nakiyanakiya
1134
$endgroup$
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14
add a comment |
$begingroup$
Suppose I have a set of triangle numbers A = {1, 3, 6, 10 ...} (2000 items)
I want to find the pair of numbers in AxA (i.e. 1*3, 1*6, 3*6..., a*b,...) where the product a*b is closest to N. (N = 2000000).
What I tried was to generate the pairs of numbers and then get abs(N - a*b) and sort, and find first pair. But I find it too slow.
Is technique I can use here to easily arrive at an answer?
combinatorics
asked Jan 23 at 3:01
nakiyanakiya
1134
$endgroup$
Suppose I have a set of triangle numbers A = {1, 3, 6, 10 ...} (2000 items)
I want to find the pair of numbers in AxA (i.e. 1*3, 1*6, 3*6..., a*b,...) where the product a*b is closest to N. (N = 2000000).
What I tried was to generate the pairs of numbers and then get abs(N - a*b) and sort, and find first pair. But I find it too slow.
Is technique I can use here to easily arrive at an answer?
combinatorics
combinatorics
asked Jan 23 at 3:01
nakiyanakiya
1134
asked Jan 23 at 3:01
nakiyanakiya
1134
asked Jan 23 at 3:01
nakiyanakiya
1134
asked Jan 23 at 3:01
nakiyanakiya
1134
asked Jan 23 at 3:01
nakiyanakiya
1134
1134
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14
add a comment |
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Since no one has mentioned using triangular number properties yet:
Triangular numbers are defined as: $$T_n = frac{n(n+1)}{2}$$
Using this, product of two, $T_n cdot T_k$ would be
$$T(n,k) = T_ncdot T_k = frac{nk + n + k + 1}{4}$$
This can be calculated in $O(1)$ time.
Now set n = n, k = 1, where n = largest index available.
Now:
- Record $|N-T(n,k)|$ and if it is the minimum, store the values of n,k.
- If T(n,k) > N, set n as $frac{n+k}{2}$
- If T(n,k) < N, set k as $frac{n+k}{2}$
- If T(n,k) = N, you have your values.
After this, you will have the index values of your triangle numbers. You can reverse calculate $T_n$ and $T_k$.
Since, the entire algorithm is essentially two binary searches, the time complexity is $O(log(n))$
answered Jan 23 at 4:33
HitenHiten
1477
$endgroup$
$begingroup$
This is a great method. However, note that there might not be values forn,ksuch thatT(n,k) == N. The idea is to get as close toNas possible.
$endgroup$
– nakiya
Jan 23 at 9:18
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
add a comment |
$begingroup$
If the number of elements in the given set is $n$, then you can use hashing to obtain a $O(n)$ solution for the related problem of deciding if there exists such a pair in the given set. Below, I give the high level pseudocode of the algorithm. This should give you an idea of how to solve your problem.
- Let A be the given array of elements. Create an empty hash table H.
for i = $0$ to $n$:
(i) If A[i] == $0$ && N == $0$: return true.
(ii) Else If N % A[i] == $0$ && N/A[i] exists in H: return true.
(iii) Insert A[i] into H.
Return false
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
$endgroup$
$begingroup$
I followed something similar to this in the end. Note that the product can be close toNand not exactly equal to it. So, then a sorted hash table is needed.
$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
add a comment |
$begingroup$
If your numbers are sorted, you could "prefilter" some options by doing something like this:
Pick a number x in the sorted set A.
For different values of y in A, calculate d = abs(N- xy). Since the set is sorted, d should decrease until you find the optimal value of y, then it starts increasing.
When d increases stop iterating on values of y, pick the next x and start all over again with the values of y.
I think my answer is rather obvious but it will certainly help if you are generating all pairs before calculating the distance, which you don't need to do.
answered Jan 23 at 3:32
JaviJavi
3979
$endgroup$
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.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
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%2fmath.stackexchange.com%2fquestions%2f3084026%2fgiven-a-set-of-numbers-is-there-a-quick-way-to-find-the-two-numbers-which-their%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since no one has mentioned using triangular number properties yet:
Triangular numbers are defined as: $$T_n = frac{n(n+1)}{2}$$
Using this, product of two, $T_n cdot T_k$ would be
$$T(n,k) = T_ncdot T_k = frac{nk + n + k + 1}{4}$$
This can be calculated in $O(1)$ time.
Now set n = n, k = 1, where n = largest index available.
Now:
- Record $|N-T(n,k)|$ and if it is the minimum, store the values of n,k.
- If T(n,k) > N, set n as $frac{n+k}{2}$
- If T(n,k) < N, set k as $frac{n+k}{2}$
- If T(n,k) = N, you have your values.
After this, you will have the index values of your triangle numbers. You can reverse calculate $T_n$ and $T_k$.
Since, the entire algorithm is essentially two binary searches, the time complexity is $O(log(n))$
answered Jan 23 at 4:33
HitenHiten
1477
$endgroup$
$begingroup$
This is a great method. However, note that there might not be values forn,ksuch thatT(n,k) == N. The idea is to get as close toNas possible.
$endgroup$
– nakiya
Jan 23 at 9:18
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
add a comment |
$begingroup$
Since no one has mentioned using triangular number properties yet:
Triangular numbers are defined as: $$T_n = frac{n(n+1)}{2}$$
Using this, product of two, $T_n cdot T_k$ would be
$$T(n,k) = T_ncdot T_k = frac{nk + n + k + 1}{4}$$
This can be calculated in $O(1)$ time.
Now set n = n, k = 1, where n = largest index available.
Now:
- Record $|N-T(n,k)|$ and if it is the minimum, store the values of n,k.
- If T(n,k) > N, set n as $frac{n+k}{2}$
- If T(n,k) < N, set k as $frac{n+k}{2}$
- If T(n,k) = N, you have your values.
After this, you will have the index values of your triangle numbers. You can reverse calculate $T_n$ and $T_k$.
Since, the entire algorithm is essentially two binary searches, the time complexity is $O(log(n))$
answered Jan 23 at 4:33
HitenHiten
1477
$endgroup$
$begingroup$
This is a great method. However, note that there might not be values forn,ksuch thatT(n,k) == N. The idea is to get as close toNas possible.
$endgroup$
– nakiya
Jan 23 at 9:18
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
add a comment |
$begingroup$
Since no one has mentioned using triangular number properties yet:
Triangular numbers are defined as: $$T_n = frac{n(n+1)}{2}$$
Using this, product of two, $T_n cdot T_k$ would be
$$T(n,k) = T_ncdot T_k = frac{nk + n + k + 1}{4}$$
This can be calculated in $O(1)$ time.
Now set n = n, k = 1, where n = largest index available.
Now:
- Record $|N-T(n,k)|$ and if it is the minimum, store the values of n,k.
- If T(n,k) > N, set n as $frac{n+k}{2}$
- If T(n,k) < N, set k as $frac{n+k}{2}$
- If T(n,k) = N, you have your values.
After this, you will have the index values of your triangle numbers. You can reverse calculate $T_n$ and $T_k$.
Since, the entire algorithm is essentially two binary searches, the time complexity is $O(log(n))$
answered Jan 23 at 4:33
HitenHiten
1477
$endgroup$
Since no one has mentioned using triangular number properties yet:
Triangular numbers are defined as: $$T_n = frac{n(n+1)}{2}$$
Using this, product of two, $T_n cdot T_k$ would be
$$T(n,k) = T_ncdot T_k = frac{nk + n + k + 1}{4}$$
This can be calculated in $O(1)$ time.
Now set n = n, k = 1, where n = largest index available.
Now:
- Record $|N-T(n,k)|$ and if it is the minimum, store the values of n,k.
- If T(n,k) > N, set n as $frac{n+k}{2}$
- If T(n,k) < N, set k as $frac{n+k}{2}$
- If T(n,k) = N, you have your values.
After this, you will have the index values of your triangle numbers. You can reverse calculate $T_n$ and $T_k$.
Since, the entire algorithm is essentially two binary searches, the time complexity is $O(log(n))$
answered Jan 23 at 4:33
HitenHiten
1477
answered Jan 23 at 4:33
HitenHiten
1477
answered Jan 23 at 4:33
HitenHiten
1477
answered Jan 23 at 4:33
HitenHiten
1477
1477
$begingroup$
This is a great method. However, note that there might not be values forn,ksuch thatT(n,k) == N. The idea is to get as close toNas possible.
$endgroup$
– nakiya
Jan 23 at 9:18
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
add a comment |
$begingroup$
This is a great method. However, note that there might not be values forn,ksuch thatT(n,k) == N. The idea is to get as close toNas possible.
$endgroup$
– nakiya
Jan 23 at 9:18
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
$begingroup$
This is a great method. However, note that there might not be values for
n, k such that T(n,k) == N. The idea is to get as close to N as possible.$endgroup$
– nakiya
Jan 23 at 9:18
$begingroup$
This is a great method. However, note that there might not be values for
n, k such that T(n,k) == N. The idea is to get as close to N as possible.$endgroup$
– nakiya
Jan 23 at 9:18
1
1
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
@nakiya Thus there was the first step... every time you change the value of n or k, you find the absolute difference between T and N, see if it is smaller than all other T’s so far, and keep track of it
$endgroup$
– Hiten
Jan 23 at 11:48
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
Can the same time complexity be maintained? What would be the stopping condition of the search?
$endgroup$
– nakiya
Jan 23 at 13:14
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
$begingroup$
@nakiya when n>= k should be the stoping condition. Yes, the complexity should be log(n)... as I said, two binary searches at each stage of the binary search you do constant operations.
$endgroup$
– Hiten
Jan 23 at 13:34
add a comment |
$begingroup$
If the number of elements in the given set is $n$, then you can use hashing to obtain a $O(n)$ solution for the related problem of deciding if there exists such a pair in the given set. Below, I give the high level pseudocode of the algorithm. This should give you an idea of how to solve your problem.
- Let A be the given array of elements. Create an empty hash table H.
for i = $0$ to $n$:
(i) If A[i] == $0$ && N == $0$: return true.
(ii) Else If N % A[i] == $0$ && N/A[i] exists in H: return true.
(iii) Insert A[i] into H.
Return false
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
$endgroup$
$begingroup$
I followed something similar to this in the end. Note that the product can be close toNand not exactly equal to it. So, then a sorted hash table is needed.
$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
add a comment |
$begingroup$
If the number of elements in the given set is $n$, then you can use hashing to obtain a $O(n)$ solution for the related problem of deciding if there exists such a pair in the given set. Below, I give the high level pseudocode of the algorithm. This should give you an idea of how to solve your problem.
- Let A be the given array of elements. Create an empty hash table H.
for i = $0$ to $n$:
(i) If A[i] == $0$ && N == $0$: return true.
(ii) Else If N % A[i] == $0$ && N/A[i] exists in H: return true.
(iii) Insert A[i] into H.
Return false
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
$endgroup$
$begingroup$
I followed something similar to this in the end. Note that the product can be close toNand not exactly equal to it. So, then a sorted hash table is needed.
$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
add a comment |
$begingroup$
If the number of elements in the given set is $n$, then you can use hashing to obtain a $O(n)$ solution for the related problem of deciding if there exists such a pair in the given set. Below, I give the high level pseudocode of the algorithm. This should give you an idea of how to solve your problem.
- Let A be the given array of elements. Create an empty hash table H.
for i = $0$ to $n$:
(i) If A[i] == $0$ && N == $0$: return true.
(ii) Else If N % A[i] == $0$ && N/A[i] exists in H: return true.
(iii) Insert A[i] into H.
Return false
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
$endgroup$
If the number of elements in the given set is $n$, then you can use hashing to obtain a $O(n)$ solution for the related problem of deciding if there exists such a pair in the given set. Below, I give the high level pseudocode of the algorithm. This should give you an idea of how to solve your problem.
- Let A be the given array of elements. Create an empty hash table H.
for i = $0$ to $n$:
(i) If A[i] == $0$ && N == $0$: return true.
(ii) Else If N % A[i] == $0$ && N/A[i] exists in H: return true.
(iii) Insert A[i] into H.
Return false
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
edited Jan 23 at 4:02
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
answered Jan 23 at 3:55
Novice GeekNovice Geek
3811
3811
$begingroup$
I followed something similar to this in the end. Note that the product can be close toNand not exactly equal to it. So, then a sorted hash table is needed.
$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
add a comment |
$begingroup$
I followed something similar to this in the end. Note that the product can be close toNand not exactly equal to it. So, then a sorted hash table is needed.
$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
$begingroup$
I followed something similar to this in the end. Note that the product can be close to
N and not exactly equal to it. So, then a sorted hash table is needed.$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
I followed something similar to this in the end. Note that the product can be close to
N and not exactly equal to it. So, then a sorted hash table is needed.$endgroup$
– nakiya
Jan 23 at 4:10
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
$begingroup$
@nakiya exactly!!
$endgroup$
– Novice Geek
Jan 23 at 4:13
add a comment |
$begingroup$
If your numbers are sorted, you could "prefilter" some options by doing something like this:
Pick a number x in the sorted set A.
For different values of y in A, calculate d = abs(N- xy). Since the set is sorted, d should decrease until you find the optimal value of y, then it starts increasing.
When d increases stop iterating on values of y, pick the next x and start all over again with the values of y.
I think my answer is rather obvious but it will certainly help if you are generating all pairs before calculating the distance, which you don't need to do.
answered Jan 23 at 3:32
JaviJavi
3979
$endgroup$
add a comment |
$begingroup$
If your numbers are sorted, you could "prefilter" some options by doing something like this:
Pick a number x in the sorted set A.
For different values of y in A, calculate d = abs(N- xy). Since the set is sorted, d should decrease until you find the optimal value of y, then it starts increasing.
When d increases stop iterating on values of y, pick the next x and start all over again with the values of y.
I think my answer is rather obvious but it will certainly help if you are generating all pairs before calculating the distance, which you don't need to do.
answered Jan 23 at 3:32
JaviJavi
3979
$endgroup$
add a comment |
$begingroup$
If your numbers are sorted, you could "prefilter" some options by doing something like this:
Pick a number x in the sorted set A.
For different values of y in A, calculate d = abs(N- xy). Since the set is sorted, d should decrease until you find the optimal value of y, then it starts increasing.
When d increases stop iterating on values of y, pick the next x and start all over again with the values of y.
I think my answer is rather obvious but it will certainly help if you are generating all pairs before calculating the distance, which you don't need to do.
answered Jan 23 at 3:32
JaviJavi
3979
$endgroup$
If your numbers are sorted, you could "prefilter" some options by doing something like this:
Pick a number x in the sorted set A.
For different values of y in A, calculate d = abs(N- xy). Since the set is sorted, d should decrease until you find the optimal value of y, then it starts increasing.
When d increases stop iterating on values of y, pick the next x and start all over again with the values of y.
I think my answer is rather obvious but it will certainly help if you are generating all pairs before calculating the distance, which you don't need to do.
answered Jan 23 at 3:32
JaviJavi
3979
answered Jan 23 at 3:32
JaviJavi
3979
answered Jan 23 at 3:32
JaviJavi
3979
answered Jan 23 at 3:32
JaviJavi
3979
3979
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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');
});
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%2fmath.stackexchange.com%2fquestions%2f3084026%2fgiven-a-set-of-numbers-is-there-a-quick-way-to-find-the-two-numbers-which-their%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');
});
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');
});
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');
});
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
$begingroup$
Have you tried using the fact that triangle numbers can be represented as their indices, and hence you could minimize a quadratic in logarithmic time by using binary search?
$endgroup$
– Hiten
Jan 23 at 4:14