How to split a number in two, each of which lie within a range?

Question

While attempting a question, I was required to split a number 'n' into 2 parts, each part falling within a given range (inclusive).

There can be more than one solution obviously, only one is required.

Example - n = 5 and Range = 2 to 4

       Solutions would be (2,3) (3,2)

It's easy in the head but unable to derive a quick logic. Thank you

Language - C++

What language are you working in? And also your example contradicts the premise - (1,4) and (4,1) do not have *both* parts in the range 2 to 4, so you would actually only expect (2,3), (3,2) ? — James Casey, Dec 01 '16 at 15:13
where is 1,4 in the range 2,4? or do i misunderstand what you mean with range? also which prpgramming languege you want to have? — XtremeBaumer, Dec 01 '16 at 15:13

score 1 · Answer 1 · edited May 20 '21 at 06:38

1

#include<bits/stdc++.h>

using namespace std;

int main(){

int l,r,s;

cin>>l>>r>>s;    //here l & r are range & s is sum that we want to split

if(2 * r < s){

cout<<0<<endl;

return 0;

}

int start,end;

start = s - l;

if(start > r){

start -= r;

start += l;

}

end = s-start;

int count = abs(end - start) + 1;

cout<<count<<endl;

return 0;

}

edited May 20 '21 at 06:38

StupidWolf

45,075
17
40
72

answered May 20 '21 at 05:28

Shubham Gupta

11
2

Kirill Bulygin · Accepted Answer · 2016-12-01T16:07:10.370

0

For each part to fall "within a given range (inclusive)", the solutions for n = 5 and Range = 2 to 4 would be (2,3), (3,2).

The most trivial solution is like this:

for i = range_min to range_max:
    if range_min <= n - i <= range_max:
        print (i, n-i)

Update. A deeper analysis:

a = range_min
b = range_max

a <= i <= b

a <= n - i <= b
a - n <= -i <= b - n
-a + n >= i >= -b + n
n - b <= i <= n - a

max(a, n-b) <= i <= min(b, n-a)

for i = max(a, n-b) to min(b, n-a):
    print (i, n-i)

There is nothing more efficient possible, as anyway you need to loop through all the matching pairs at least to print them, and here there is only printing.

Update 2. Only one pair (if exists) and in C++:

#include <iostream>
#include <algorithm> // min, max
using namespace std;

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    int lo = max(a, n-b);
    int hi = min(b, n-a);
    if (lo <= hi) {
        cout << "(" << lo << ", " << n - lo << ")" << endl;
    } else {
        cout << "nope" << endl;
    }
    return 0;
}

edited Dec 01 '16 at 16:07

answered Dec 01 '16 at 15:12

Kirill Bulygin

3,658
1
17
23

There's nothing more efficient than a loop, I suppose? – borb183 Dec 01 '16 at 15:28
Updated the answer. – Kirill Bulygin Dec 01 '16 at 15:51
I'm sorry not very familiar with python (if this is that :P). Do these operations exist in c++? – borb183 Dec 01 '16 at 15:56
Also, if I only had to find the first occurrence and stop there (not print other combinations), would this be better? – borb183 Dec 01 '16 at 15:57
That's just a "quick logic", such operations certainly do exist in C++. Didn't notice this part in your question: "There can be more than one solution obviously, only one is required", you can `break` after the `print` (will update the answer). – Kirill Bulygin Dec 01 '16 at 16:02

score 0 · Answer 3 · answered Dec 01 '16 at 15:20

0

You haven't specified a language to use, so here's a very basic implementation with JavaScript:

var n = 5;
for (var i = 0; i < n-1; i++) {
  var first = i + 1;
  var second = n-i-1;
  console.log('(' + first + ',' + second + ')' + ' ' + '(' + second + ',' + first + ')' );
}

Hope that helps!

answered Dec 01 '16 at 15:20

Dave Cooper

10,494
4
30
50

Ah I just saw your edit - my answer is out of date now :P – Dave Cooper Dec 01 '16 at 15:20
Haha ya, was a typo – borb183 Dec 01 '16 at 15:46

score 0 · Answer 4 · answered Dec 01 '16 at 15:25

I suggest enumeration instead of splitting:

Validate the input: to >= from, value >= 2 * from, value <= 2 * to
Start from value - to or from
Return while both parts in [from..to] range

Sample C# 6.0 solution

public static IEnumerable<Tuple<int, int>> Ranges(int value, int from, int to) {
  if (to < from) // empty range
    yield break;
  else if (value < 2 * from || value > 2 * to) // value is too small or too big
    yield break;

  // start either from left border or from minumum possible value within the range
  int start = value - to >= from ? value - to : from;

  // both i and value - i should be in [to..from] range
  for (int i = start; i <= to && value - i >= from; ++i) 
    yield return new Tuple<int, int>(i, value - i); // (i, value - i) pair
}

Test:

var result = Ranges(5, 2, 4)
  .Select(range => $"({range.Item1},{range.Item2})");

Console.Write(string.Join(" ", result));

Outcome:

(3,4) (4,3)

Is the complexity of this better than O(from - to) ? This forms a small part of the code. Better to have a simple implementation — borb183, Dec 01 '16 at 15:43
@borb183: it's not *complexity* that matters, but *validation*. E.g. `(6, 8, 9)` as well as `(6, 1, 2)` should return *nothing*; `(6, 1, 3)` should return `(3, 3)` only etc. — Dmitry Bychenko, Dec 01 '16 at 15:47
Needed to use in competitive coding, thus efficiency did matter. Otherwise yes, it's good — borb183, Dec 01 '16 at 15:51

How to split a number in two, each of which lie within a range?

4 Answers4