Calculating using modulus [closed]

Question

I am working on a problem: The user enters 3 tree heights and also the tree height limit. The program then calculates the amount of tree to remove.

Sample input:

 Tree1: 14
 Tree2: 7
 Tree3: 16

 Tree limit: 11

Sample output:

 Amount to remove: 8

This would usually not be too bad for me although I am still a beginner but the problem is, I am going to be calculating it WITHOUT an if statement. I must use Modulus to calculate. I have spent a very long time researching and trying different things but I just cannot seem to get it? Any ideas?

Fresno

Can you post Code of your best try ? – Hath

Can you still use ternary statements? – Rooted

what do you mean by "without if statement"? No branching at all? Can you use loops? – Rowles

I bet you can use addition and subtraction as well as modulo arithmetic... – Illtreat

@nos Amount to remove = (Tree1 - 11) + (Tree3 - 11). We omit Tree2 because it is <= 11. – Carper

n = tree - (tree % limit) will only work for tree excesses less than the limit. – Heinrik

@Carper Whoops. I was working solution possibilities in my head and that was the transient at the time. I shouldn't think and type at the same time. Sorry. – Flail

@Flail no worries, I've had a few too many mistakes slip thru too recently. – Carper

if is the correct tool. Other things are silly games that are not very helpful for actually learning anything. – Lanneret

You have stated that if is not allowed. What about while or for statements? – Crust

@Fresno - Can you edit your question so that it is clear what you have already tried and which assumptions should be made, i.e. which operators/statements are allowed – Perseus

Answer 1

The expression you're looking for is:

tree[i] % max % tree[i];

When tree[i] is greater than max:
example: 16 and 11

16 % 11 = 5
5 % 16 = 5

But when tree[i] is less than max:
example: 7 and 11

7 % 11 = 7
7 % 7 = 0

int main(void)
{
    int tree[3] = {0};
    int max = 0;
    int cut = 0;

    printf("Max Height: "),
    scanf("%d", &max);

    for(int i=0; i<3; ++i)
    {
        printf("Tree%d: ",i+1),
        scanf("%d", &tree[i]);
    }

    for(int i=0; i<3; ++i)
    {
        cut += (tree[i] % max) % tree[i];
    }
    printf("Amount to remove: %d\n", cut);

    getchar();
    return 0;
}

---

In August 2015 (nearly 2 years from the original post), I decided to revisit this question, and come up with a generalized solution.

It look a little work, but the full expression is:

int cut = (tree % max % tree) + !!(tree/max) * (tree/max - 1) * max;

Examples:

| Tree | Max | Expression      | Answer |
|    4 |  11 | 0 + 0 * -1 * 11 |      0 |
|   47 |  11 | 3 + 1 * 3 * 11  |     36 |

Note: My use of !! (double-not) is pretty much a C / C++ only construct. May not work in other languages.

Decane

+1, probably handles the OP's case, but unfortunately this only holds until tree[i] >= n*max where n > 1. The answer will include integer division and modulo, but this puts the OP on the closest track. – Heinrik

Will this work if tree[i] is, say, 25? You'd get an answer of 3 from the modulus calculations. – Resoluble

+1 for the statement x%max%x. But an edit to fix the range problem would be good. Range in your solution is only good for 0<tree<2*tree. (as pointed out by several commenting on this post) – Crust

2015: I updated my post with a generalized expression. It involves 4 terms overall, and a double-not. But it doesn't have the same domain-problem. – Decane

Answer 2

Here's a general solution:

#include <stdio.h>

#define CUTAMOUNT(tr, lim) (tr - lim) * (((2 * tr) - ((2 * tr) % (tr + lim))) / (tr + lim - 1))

int main (int argc, char **argv) {

    int tree1 = 14;
    int tree2 = 7;
    int tree3 = 16;
    int limit = 11;

    int cutamounttotal = 0;

    cutamounttotal += CUTAMOUNT(tree1, limit);
    cutamounttotal += CUTAMOUNT(tree2, limit);
    cutamounttotal += CUTAMOUNT(tree3, limit);

    printf("Amount to remove: %d\n", cutamounttotal);

    return 0;
}

• no branches
• no loops
• no conditionals
• no ternary operations
• no bitwise operations
• no logic operations

Only arithmetic operations. The trick is to understand that % is the only arithmetic operator which can create a step. Operands must be sized appropriately to ensure the step only occurs where we want it and nowhere else. We can then exploit that step to give the desired result.

Perseus

Flawless! Gladly eating my words as we speak. – Valerie

Answer 3

You can do it using only absolute value function(abs), division, subtraction, addition.

Tree1: 14
Tree2: 7
Tree3: 16

Tree limit: 11

14-11=3 ----->3+abs(3)=6  ----------> 6/2 =3
7-11=-4 ----> -4 + abs(-4)=0 -------------> 0/2=0
16-11=5 -----> 5+abs(5)=10 ------------> 10/2 = 5
...
...
...
3+5 = 8 :D

The upper text shows how you convert smaller values to zero. So only bigger values are additively effective.

If you cannot use abs() then you can shift-left + shift-right combo to get absolute value. But this can go undefined behaviour. Results are implementation-defined for right-shifts of signed values.

Seabury

Probably the most general answer, but it just hides the implementation in the abs() function, which still must either use if, or some kind of trick with bit-shifting or conditionals. – Valerie

Not always, it can use the msb bit to broadcast or multiply. For example, Val * msb.AND.1 is the thing. – Seabury

"Some kind of trick with bit-shifting or conditionals", in other words. – Valerie

Yea, I just couldnt find the exact fiddling :) – Seabury

If we cannot hide "if", how others cannot hide cpu-level hardware "if" s ? Shifting left by 1 bit and shifting right by 1 bit just makes msb zero :P – Seabury

Hey, it's not my question - I'd just use if. – Valerie

Can shifting left by 1 time and shifting right by one time, clear the msb always? – Seabury

No, left shifting negative numbers is undefined. Right shifting a negative number is implementation defined. – Valerie

What about including an assembly code from another package that uses cpu-level shifting instructions? – Seabury

Then it wouldn't be C, and the whole question would be moot. – Valerie

Okay, can signum function be "if"less ? I suspect it would be same with abs() – Seabury

If you can't call abs why not use bit magic to get MAX(treeSize, limit) and call it a day? – Heinrik

Answer 4

I'm a little disappointed in myself for giving this question so much thought, but that being said, I'm going to go out on a limb and say there is no general solution for all n > 0 that either doesn't use an if statement, or doesn't use some other kind of trickery to simulate one. I'll gladly eat my words if someone demonstrates me wrong.

For each tree, the obvious and correct solution is:

cut = max(height - limit, 0);

which is equivalent to:

if ( height - limit > 0 ) {
   cut = height - limit;
} else {
   cut = 0;
}

or alternatively:

if ( height > limit ) {
   cut = height - limit;
} else {
   cut = 0;
}

The simplest way (other than using a max() function) to simulate this without actually explicitly using an if statement is:

cut = (height - limit) * (height > limit);

since height > limit will evaluate to 1 or 0 at the right times.

You can also simulate it with a while loop as so:

cut = 0;
while ( height > limit ) {
   cut = height - limit;
   break;
}

and using a ternary operator is the most blatant way to claim to not use an if. There may be other tricks messing with bits, but the story is the same.

It's possible to modify any of these methods to employ the modulo operator as the question asks, but all that achieves is making a simpler algorithm more complex.

I suspect the method in abelenky's answer is the one that's being sought and probably the best overall solution to the question, here, even though it only works for 0 < n < 2 * limit.

Valerie

+1 Best solution. cut = (height - limit) * (height > limit) – Crowder

Answer 5

Let's say you've already read in the 3 tree heights into an array:

int trees[3];
int limit = 11;
int i;
int cut = 0;
for (i = 0; i < 3; i++) {
    int cut += trees[i] > limit
             ? (trees[i] / limit - 1) * limit + trees[i] % limit
             : 0;
}
printf("Amount to remove: %d\n", cut);

Loom

that's going to return number of trees that need to be cut, not total length to be cut. – Rowles

Answer 6

[EDIT] - Solution for all values of tree, uses % operator, but not ternary:

#include <stdio.h>

#define MAX 11

int modsum(int a, int b, int c) ;

int main()
{
    int results;
    results = modsum(25, 7, 16);
    return 0;
}

int modsum(int a, int b, int c)
{
    int i, suma, sumb, sumc;

    i=0;
    while(a > 2*MAX)
    {
        i++;
        a -= MAX;
    }
    suma = (i*MAX)+(a%MAX%a);

    i=0;
    while(b > 2*MAX)
    {
        i++;
        b -= MAX;
    }
    sumb = (i*MAX)+(b%MAX%b);

    i=0;
    while(c > 2*MAX)
    {
        i++;
        c -= MAX;
    }
    sumc = (i*MAX)+(c%MAX%c);


    return suma+sumb+sumc;

}

Crust

How is "a>11 ? " different from "if staement"? – Rowles

@MK - It does depend on using the ternary operator, yes, but OP has not answered whether it is out of bounds to do so. – Crust

ternary operator and if are the same thing. – Rowles

See edit, provide solution for all values of tree without ternary. – Crust

Using while is still cheating, if if isn't allowed. Instead of if ( h > max ) { cut = h - max; } else { cut = 0; } you could just do cut = 0; while ( h > max ) { cut = h - max; break; } Just goes to show what a silly problem this is. – Valerie

@PaulGriffiths - agreed on the silly part. But there is a fundamental difference between a keyword that branches and one that loops, no? Maybe the OP's constraints are designed to teach looping on modulus operators. Who knows – Crust

@ryyker: Well, there's a fundamental difference between a loop and an if statement, for sure, but a loop is just a conditional branch that's tested, potentially, more than once. I suspect that abelenky's answer is the one that's actually expected by the assignment, or close to it, even though it works only for a limited domain. – Valerie

@PaulGriffiths - abelsnky's answer also uses loops. More importantly, there is nothing in the OP description that inhibits use of loops. I am just not sure how you are deriving this requirement. – Crust

@ryyker: abelenky's solution only uses loops to sum the results for the three trees, it doesn't use loops to calculate the cut for each individual tree. It's not my requirement, but the way I see it, it's pointless forbidding an if but permitting something functionally identical to an if, which a loop is as I showed. Same reason the simplest answer, cut = (h - max) * (h > max); shouldn't be permitted, because that last * (h > max) is functionally identical to if ( h > max ) in this context. – Valerie

Answer 7

Assuming you are allowed to use *, /, and >, you can do it like so:

#include <stdio.h>

int main()
{
  int trees[3] = {24, 7, 16};
  int limit = 11;
  int allowedRemainder = 0;
  int mod = 0;
  int modCount = 0;
  int i;
  for (i = 0; i < 3; ++i)
  {
    allowedRemainder = (trees[i] / limit) - 1;
    mod = trees[i] % limit;

    modCount += (allowedRemainder > 0) * (allowedRemainder * limit) +
                (allowedRemainder >= 0) * mod;
    printf("Loop %d: mod = %d\n", i, modCount);
  }
  printf("Amount to remove: %d\n", modCount);
  return 0;
}

(allowedRemainder > 0) * (allowedRemainder * limit) says if we had at least limit more than allowed, add a multiple of limit to modCount. (allowedRemainder >= 0) * mod says if we had more than limit, add the remainder to modCount.

[Sample Code]

Grange

This also only works when tree[n] < (limit * 2). If tree[0] was 30, for instance, then you end up with 8 * 1. – Valerie

@PaulGriffiths: Good point, I fixed the logic to deal with that. – Grange

Answer 8

Tree heights are in an array, because I'm too lazy to make 3 variables.
It makes use of modulo operator as requested.

#include <stdio.h>

int main(void)
{
  int tree_h[]={14,7,16};
  int limit=11;
  int i;
  int remove=0;

  for(i=0;i<3;i++)
  {
    remove+=(tree_h[i]>limit)*(tree_h[i]%limit);
  }
  printf("Amount to remove: %d\n", remove);

  return 0;
}

Almandine