[Math] programming brain teaser

algorithmspuzzle

Given a programming language where you could make as many variables up as possible and you could only perform these three operators find b-1.

a=0;
b++;
loop(c){  // This loop will loop exactly c times

}

an example to find the number 2.

a = 0;
a ++;
a ++; // 2

How would you find b-1, where b is any positive integer? There are no signed numbers in this language.

Best Answer

It seems that the trick to this question is that for c = 0, loop(c){} loops zero times, ie does nothing. Therefore the following program will work:

a=0;
c=0;
loop(b){
  loop(c){
    a++;
  }
  c=0;
  c++;
}

We end up with b-1 in a.

Related Solutions

[Math] Algorithm for computing powers

squared exponentiation is the way to go here

BigInt pow(BigInt a,BigInt n){
    BigInt r= 1;
    while(n>0){
        if(mod(n,2)==1)r=mult(r,a);
        a=mult(a,a);
        n=div(n,2);
    }
    return r;
}

here mod(a,b) is the remainder of a/b mult(a,b) is a*b and div(a,b) is floor(a/b)

this relies on $a^n = {a^2}^{\lfloor \frac{n}{2}\rfloor }\cdot \begin{cases} a & \mbox{if }n\mbox{ is even}\\1 & \mbox{if }n\mbox{ is odd}\end{cases}$

or more precisely

$$a^n=\prod_{i=0}^{\lfloor\log n\rfloor}{\begin{cases} a^{2^i} & \mbox{if }\Big\lfloor \frac{n}{2^i}\Big\rfloor\mbox{ is even}\\1 & \mbox{if }\Big\lfloor \frac{n}{2^i}\Big\rfloor\mbox{ is odd}\end{cases}} $$

Best Answer

Related Solutions

[Math] Algorithm for computing powers

Related Question