CODEWITHSUNDEEP
splitintegersumrange
borb183
borb183

Reputation: 53

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

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++

Upvotes: 0

Views: 208

Answers (4)

Shubham Gupta
Shubham Gupta

Reputation: 11

#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;

}

Upvotes: 1

Kirill Bulygin
Kirill Bulygin

Reputation: 3826

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;
}

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

I suggest enumeration instead of splitting:

  1. Validate the input: to >= from, value >= 2 * from, value <= 2 * to
  2. Start from value - to or from
  3. 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)

Upvotes: 0

Dave Cooper
Dave Cooper

Reputation: 10714

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!

Upvotes: 0

Related Questions