Calculating using modulus [closed]

Question 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.

Question 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.

Question 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.

Question 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.

Question 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);

Question 6

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]

Question 7

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

}

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