Problem of the Day -- No Divide

No Divide

No this isn't a reference to that Linkin Park song. Today's your Introduction to Computer Science mid-term. You're doing alright on the test and the last question is "implement a function that takes in 2 integers and returns the division of the 2 numbers rounded to the nearest integer".

Piece of cake you say. As you're typing it up you exclaim "what the heck", which gets you some really weird stares. You've just learned that your "/" key is broken. Some of you that are having a really bad day learn that your "/", "*", "+", and "-" are all broken. How can we solve this problem without using any of your broken keys? Note: You're using a pirated version of Windows 2015 so your copy and paste functionality is also broken.

Permalink: http://problemotd.com/problem/no-divide/

Comments:

Steve Mostovoy - 10 years, 9 months ago
One liner... this is fair, right? :)
```
return (int)Decimal.Round(Decimal.Divide(numerator, denominator));
```
reply permalink

Adam - 10 years, 9 months ago

Pretty easy in Python:

def div(a, b):
     return round(operator.div(a, b))

Closest I could get in C:

return (int) nearbyint(exp(log(a) - log(b)));

reply permalink

Adam - 10 years, 9 months ago
Whoops, the Python needs to be "return round(operator.div(float(a), float(b)))". This only works in Python 2. Python 3 would use operator.truediv.

reply permalink
Pearce Keesling - 10 years, 9 months ago
Check this method out, it might solve your problem :)

http://www.cplusplus.com/reference/cmath/fma/

reply permalink

Pearce Keesling - 10 years, 9 months ago

Had to go digging through the documentation for that one. So far cmath has never let me down :)

#include <iostream>
#include <cmath>
#include <sstream>

using namespace std;

int main(int argc, char *argv[])
{
    int num,den;
    stringstream(argv[1]) >> num;
    stringstream(argv[2]) >> den;
    cout << round(fma(num,pow(den,log10(0.1)), 0)) <<     endl;
    return 0;
}

reply permalink

Carlos - 10 years, 9 months ago

This doesn't work for negative numbers i believe, the results on the floored version may seem at first glance but, if you run the not floored version with the same parameters, sometimes the java rounds downs by a few nano units or something

public static void main(String[] args) {
    testCase();
}

public static void testCase() {
    System.out.println("Not floored: ");
    System.out.println("4 / 2 = " + specialDivision(4, 2));
    System.out.println("16 / 2 = " + specialDivision(16, 2));
    System.out.println("128 / 41 = " + specialDivision(128, 41));
    System.out.println("12 / 15 = " + specialDivision(12, 15));
    System.out.println("Floored: ");
    System.out.println("4 / 2 = " + specialDivisionFloored(4, 2));
    System.out.println("16 / 2 = " + specialDivisionFloored(16, 2));
    System.out.println("128 / 41 = " + specialDivisionFloored(128, 41));
    System.out.println("12 / 15 = " + specialDivisionFloored(12, 15));
}

public static double specialDivision(double dividend, double divisor) {
    return (Math.exp(Math.log(dividend) - Math.log(divisor)));
}

public static double specialDivisionFloored(double dividend, double divisor) {
    return Math.floor(specialDivision(dividend, divisor));
}

reply permalink

Carlos - 10 years, 9 months ago
may seem wrong at first*

reply permalink
Eli - 10 years, 9 months ago
Maybe I always look for a solution that is too easy/lazy. I'd just pop up the virtual keyboard and use it to enter the characters. In fact, I've had to do this before.

reply permalink
Andy - 10 years, 9 months ago
More ways than one to represent "/" :)
int divide(float x, float y) { return Math.round(x \u002F y); }

reply permalink

gulliver - 10 years, 9 months ago

Here is what I came up with:

def no_divide(int1,int2):
    list2 = [0 for i in range(int2)]
    starting_length_list2 = len(list2)
    temp_list = list2[:]
    counter = []
    while (int1 >= len(temp_list)):
        for i in range(int2):
            temp_list.append(0)
        counter.append(0)
    return len(counter)

reply permalink

gulliver - 10 years, 9 months ago
whoops, ignore the line with starting_length_list2 - meant to delete that...

reply permalink
gulliver - 10 years, 9 months ago
cleaned it up a little... def no_divide(int1,int2): temp_list = [0 for i in range(int2)] counter = [] while (int1 >= len(temp_list)): for i in range(int2): temp_list.append(0) counter.append(0) return len(counter)

reply permalink

John - 10 years, 9 months ago

Javascript is so cheating...

function divide(t,b) {
   return Math.round(eval([t,String.fromCharCode(47),b].join('')));
}

reply permalink

Hueho - 10 years, 9 months ago

In Ruby it's a one liner:

def divide(a, b) a.quo(b).round end

In C it's a extremely complex operation, very low level and stuff... =)

#include <stdio.h>
#define BIT(n) (1 << n)
#define SET(num, n) (num |= BIT(n))
#define CLR(num, n) (num &= ~(BIT(n)))
#define GET(num, n) (num & (BIT(n)))
#define TOG(num, n, val) do { if(val) { SET(num, n); } else { CLR(num, n); } } while(0)
#define LOG(x) printf("%d\n", x)
int increment(int i) {
  int mask = 1;
  while(i & mask)
  {
    i &= ~mask;
    mask <<= 1;
  }
  i |= mask;
  return i;
}
int negative(int i) {
  return increment(~(i));
}
int add(int a, int b) {
  int result = 0, carry = 0;
  for(int i = 0; i < 32; i = increment(i)) {
    int bit1 = GET(a, i), bit2 = GET(b, i);
    if(bit1 && bit2) {
      TOG(result, i, 0 || carry);
      carry = 1;
    } else if(bit1 || bit2) {
      TOG(result, i, 1 || carry);
      carry = 0;
    } else {
      TOG(result, i, 0 || carry);
      carry = 0;
    }
  }
  return result;
}
int subtract(int a, int b) {
  int result = 0, carry = 0;
  for(int i = 0; i < 32; i = increment(i)) {
    int bit1 = GET(a, i), bit2 = GET(b, i);
    if(bit1 && bit2) {
      CLR(result, i);
      carry &= 1;
    } else if(bit1) {
      TOG(result, i, !(1 && carry));
      carry = 0;
    } else if(bit2) {
      TOG(result, i, 1 && carry);
      carry = 1;
    } else {
      TOG(result, i, carry);
      carry = 0;
    }
  }
  return result;
}
int aprox(int a, int b) {
  int steps_sub = 0, steps_add = 0;
  int c1 = a;
  while(c1 < b) {
    c1 = increment(c1);
    steps_add = increment(steps_add);
  }
  int c2 = a;
  while(c2 > 0) {
    c2 = subtract(c2, 1);
    steps_sub = increment(steps_sub);
  }
  return steps_sub > steps_add ? 0 : 1;
}
int divide(int a, int b) {
  int quotient = 0, partial = a;
  do {
    partial = subtract(partial, b);
    quotient = increment(quotient);
  } while(partial > b);
  return quotient + aprox(partial, b);
}
int main() {
  printf("%d\n", divide(4, 2));
}

reply permalink

Hueho - 10 years, 9 months ago
Oh, the C version only works with positive numbers, but cmon, the teacher was going too hard asking for the whole integer division.

reply permalink
Max Burstein - 10 years, 9 months ago

Very impressive on the C version. I like that you went for implementing your own add and subtract functionality.

reply permalink
Isi - 10 years, 9 months ago
Hey, it's the first time I see you post so I just wanted to thank you for making this site - it has been my motivation to program again for a while now. One of my recent favorite was the Vigenere Cipher, got any similar tasks? It was really fun experimenting with it after I coded it, and I even learned about something new while playing around.

reply permalink
Max Burstein - 10 years, 9 months ago

Glad you're enjoying the site. The vigenere cipher was one of my favorites too. I like those encryption/cracking the code problems. I have an idea for one that may end up on here next week so stay tuned!

reply permalink

Peter - 10 years, 9 months ago

def divide(x , y):
    xL = [i for i in range(x)]
    divL = []
    l = len(xL)
    while (l > y):
        for i in range(y):
            xL.pop()
        divL.append(i)
        l = len(xL)
   return len(divL)

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

No Divide

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri