[Question]
  [
**Closed**. This question needs [details or clarity](/help/closed-questions). It is not currently accepting answers.
 
 
---
**Want to improve this question?** Add details and clarify the problem by [editing this post](/posts/6836/edit).
Closed 3 years ago.
[Improve this question](/posts/6836/edit) 
Quoting [this question on SO](https://stackoverflow.com/q/11694546/698590) (Spoiler alert!):
> 
> This question has been asked in an Oracle interview.
> 
> 
> How would you divide a number by 3 without using \*, /, +, -, %,
>  operators?
> 
> 
> The number may be signed or unsigned.
> 
> 
> 
The task is solvable, but see if you can write the shortest code.
## Rules:
* Perform the required **integer** division (`/3`)
* Do not use the non-text-based operators `*`, `/`, `+`, `-`, or `%` (or their equivalents, such as `__div__` or `add()`). This also applies to incrementing and decrementing operators, like `i++` or `i--`. Use of operators for string concatenation and formatting are OK. Using these characters for different operators, such as unary `-` operator for negative numbers, or `*` to represent a pointer in C is OK as well.
* Input value can be arbitrarily large (whatever your system can handle), both positive and negative
* Input can be on STDIN or ARGV or entered any other way
* Create the shortest code you can to do the above
  
[Answer]
# C, 167503724710
Here's my solution to the problem. I admit it is unlikely to win a strict code golf competition, but it doesn't use any tricks to indirectly call built-in division functionality, it is written in portable C (as the original Stack Overflow question asked for), it works perfectly for negative numbers, and the code is exceptionally clear and explicit.
My program is the *output* of the following script:
```
#!/usr/bin/env python3
import sys
# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')
# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))
# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')
```
Character count: 71 + 39 \* 2\*\*32 + 95 = **167503724710**
### Benchmarks
It was asked how long this would take and how much memory it would use, so here are some benchmarks:
* Script execution time — Running `./test.py | pv --buffer-size=1M --average-rate > /dev/null` for about 30 seconds gives a rate of about 14.8 MB/s. The rate of output can reasonably be assumed to be roughly constant, so the running time to completion should be about 167503724710 B / (14.8 \* 1048576 B/s) ≈ 10794 s.
* Compilation time — The TCC compiler [claims to compile C code at 29.6 MB/s](http://bellard.org/tcc/#speed), which makes for a compilation time of 167503724710 B / (29.6 \* 1048576 B/s) ≈ 5397 s. (Of course this can run in a pipeline with the script.)
* Size of compiled code — I tried estimating it using `./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null`, but it seems `tcc` doesn't output anything until it reads the entire source file in.
* Memory usage to run — Since the algorithm is linear (and tcc doesn't optimize across lines), the memory overhead should be only a few kilobytes (apart from the code itself, of course).
[Answer]
# Ruby 28
```
b=->n{n.to_s(3).chop.to_i 3}
```
To divide by 3 we just need to remove the trailing zero in base 3 number:
`120 -> 11110 -> 1111 -> 40`
Works with negatives:
```
ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5
```
# Ruby, ~~60~~45
Alternatively, w/o using base conversion:
~~d=->n{x=n.abs;r=(0..1.0/0).step(3).take(x).index x;n>0?r:-r}~~
```
d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}
```
[Answer]
# Mathematica, 13 chars
```
Mean@{#,0,0}&
```
[Answer]
## JavaScript, 56
```
alert(Array(-~prompt()).join().replace(/,,,/g,1).length)
```
Makes a string of length `n` of repeating `,`s and replaces `,,,` with `1`. Then, it measures the string's resulting length. (Hopefully unary `-` is allowed!)
[Answer]
## Python, 41 38
```
print"-"[x:]+`len(xrange(2,abs(x),3))`
```
`xrange` seems to be able to handle large numbers (I think the limit is the same as for a long in C) almost instantly.
```
>>> x = -72
-24
>>> x = 9223372036854775806
3074457345618258602
```
[Answer]
# J, ~~45 44~~  10 chars
`".,&'r3'":`
Works with negatives:
```
".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99
```
`":` - format as text
`,&'r3'` - append `r3` to the end
`".` - execute the string, e.g. `15r3`
[Answer]
## Haskell, 90 ~~106~~
```
d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]
```
Creates an infinite (lazy) lookup list `[(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...]`, trims all elements that don't match `n` (`/=` is inequality in Haskell) and returns the first which does.
This gets much simpler if there are no negative numbers:
## 25 ~~27~~
```
(([0..]>>=replicate 3)!!)
```
simply returns the `n`th element of the list `[0,0,0,1,1,1,2, ...]`.
[Answer]
## C#, 232 bytes
My first code golf... And since there wasn't any C# and I wanted to try a different method not tried here, thought I would give it a shot. Like some others here, only non-negative numbers.
```
class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}
```
## Ungolfed
```
class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}
```
[Answer]
## Perl (~~26~~ 22)
```
$_=3x pop;say s|333||g
```
This version (ab)uses Perl's regex engine. It reads a number as the last command line argument (`pop`) and builds a string of `3`s of this length (`"3" x $number`). The regex substitution operator (`s///`, here written with different delimitiers because of the puzzle's rules and with a `g`lobal flag) substitues three characters by the empty string and returns the number of substitutions, which is the input number integer-divided by three. It could even be written without `3`, but the above version looks funnier.
```
$ perl -E '$_=3x pop;say s|333||g' 42
14
```
[Answer]
## C, 160 chars
Character by character long division solution using lookup tables, i.e. without string atoi() or printf() to convert between base 10 strings and integers.
Output will sometimes include a leading zero - part of it's charm.
```
main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}
```
Note:
* abuses array access to implement addition.
* compiles with clang 4.0, other compilers may barf.
Testing:
```
./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670
```
[Answer]
# Python 42
```
int(' -'[x<0]+str(len(range(2,abs(x),3))))
```
Since every solution posted here that Ive checked truncates decimals here is my solution that does that.
# Python 50 51
```
int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))
```
Since python does floor division, here is my solution that implements that.
Input integer is in the variable x. 
Tested in Python 2.7 but I suspect it works in 3 as well.
[Answer]
## JavaScript, 55
```
alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))
```
If one can't use `-1`, then here is a version replacing it with `~0` (thanks Peter Taylor!).
```
alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))
```
[Answer]
# C 83 characters
The number to divide is passed in through stdin, and it returns it as the exit code from `main()` (%ERRORLEVEL% in CMD). This code abuses some versions of MinGW in that when optimizations aren't on, it treats the last assignment value as a return statement. It can probably be reduced a bit. Supports all numbers that can fit in to an `int`
If unary negate (-) is not permitted: (129)
```
I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}
```
If unary negate **IS** permitted: (123)
```
I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}
```
# EDIT: ugoren pointed out to me that -~ is an increment...
83 Characters if unary negate is permitted :D
```
main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}
```
[Answer]
# C, 139 chars
```
t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}
```
Run with number as command line argument
* Handles both negative and positive numbers
Testing:
```
 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670
```
Edits:
* saved 10 chars by shuffling addition (A) to remove local variables.
[Answer]
## ZSH — ~~31~~ 20/21
```
echo {2..x..3}|wc -w
```
For negative numbers:
```
echo {-2..x..3}|wc -w
```
### With negative numbers (ZSH + `bc`) — ~~62~~ 61
I probably shouldn't give two programs as my answer, so here's one that works for any sign of number:
```
echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc
```
This uses the same base conversion trick as [Artem Ice's answer](https://codegolf.stackexchange.com/a/6838/1136).
[Answer]
## C, 81 73 chars
Supports non-negative numbers only.
```
char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}
```
The idea is to use pointer arithemtic. The number is read into the pointer `x`, which doesn't point anywhere. `&x[~2]` = `&x[-3]` = `x-3` is used to subtract 3. This is repeated as long as the number is above 2. `i` counts the number of times this is done (`&i[1]` = `i+1`).
[Answer]
## Java ~~86~~ 79
Assume the integer is in y:
Converts to a string in base 3, 
removes the last character ( right shift ">>" in base 3 ), 
then converts back to integer.
Works for negative numbers.
If the number, y, is < 3 or > -3, then it gives 0. 
```
System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));
```
First time posting on code golf. =) So can't comment yet.
Thx Kevin Cruijssen for the tips.
[Answer]
# Python2.6 (~~29~~)(~~71~~)(~~57~~)(~~52~~)(43)
```
z=len(range(2,abs(x),3))
print (z,-z)[x<0]
```
```
print len(range(2,input(),3))
```
Edit - Just realized that we have to handle negative integers too. Will fix that later
Edit2 - Fixed
Edit3 - Saved 5 chars by following Joel Cornett's advice
Edit4 - Since input doesn't have to be necessarily be from STDIN or ARGV, saved 9 chars by not taking any input from stdin
[Answer]
# Javascript, ~~47~~ 29
Uses `eval` to dynamically generate a `/`. Uses `+` only for string concatenation, not addition.
```
alert(eval(prompt()+"\57"+3))
```
EDIT: Used `"\57"` instead of `String.fromCharCode(47)`
[Answer]
## Ruby (~~43~~ ~~22~~ 17)
Not only golf, but elegance also :)
```
p Rational gets,3
```
Output will be like `(41/1)`. If it must be integer then we must add `.to_i` to result, and if we change `to_i` to `to_f` then we will can get output for floats also.
[Answer]
# TI-Basic, 8 bytes
Winner? :)
```
int(mean({Ans,0,0
```
P.S. Rounds towards infinity for negative numbers (see [here](https://stackoverflow.com/questions/19517868/integer-division-by-negative-number) for why). To round to zero instead, replace `int(` with `iPart(` for no byte change.
**Test cases**
```
-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36
```
[Answer]
#  Python 2.x, ~~54~~ ~~53~~ 51
`print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))`
Where `_` is the dividend and is entered as such.
```
>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6
```
Note: Not sure if using the interactive interpreter is allowed, but according to the OP: "Input can be on STDIN or ARGV or entered any other way"
Edit: Now for python 3 (works in 2.x, but prints a tuple). Works with negatives.
[Answer]
## C++, 191
With main and includes, its 246, without main and includes, it's only 178. Newlines count as 1 character. Treats all numbers as unsigned. I don't get warnings for having main return an unsigned int so its fair game.
My first ever codegolf submission.
```
#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}
```
uses shifts to divide number by 4 repeatedly, and calculates sum (which converges to 1/3)
Pseudocode:
```
// typedefs and #defines for brevity
function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.
function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).
```
As an aside, I could eliminate the main method by naming d main and making it take a char \*\* and using the programs return value as the output. It will return the number of command line arguments divided by three, rounded down. This brings its length to the advertised 191:
```
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}
```
[Answer]
## Golfscript - 13 chars
```
~3base);3base
```
[Answer]
## **PowerShell 57 or 46**
In 57 characters using `%` as the PowerShell foreach operator, not modulo. This solution can accept positive or negative integers.
```
(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length
```
In 46 characters if `*` is allowed as the string repetition operator, not multiply. This option requires positive integers as input values.
```
("1"*(Read-Host)-replace111,0-replace1).Length
```
[Answer]
# R
These only work with positive integers:
```
max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored
```
Or:
```
min(table(rep(1:3, x)[1:x]))
```
Or:
```
length((1:x)[seq(3,x,3)])
```
Or:
```
sum(rep(1,x)[seq(3,x,3)])
```
[[EDIT]] And an ugly one:
```
trunc(sum(rep(0.3333333333, x)))
```
[[EDIT2]] Plus probably the best one - inspired by the matlab code above by Elliot G:
```
length(seq(1,x,3))
```
[Answer]
# SmileBASIC, ~~58~~ ~~51~~ 36 bytes (no mathematical functions!)
```
INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)
```
Explanation:
```
INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0
```
The program moves the background layer smoothly over 3 frames, and then gets the angle after 1 frame, when it has traveled 1/3 of its total distance.
### Float division version, 38 bytes:
```
INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)
```
Explanation:
```
INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable
```
[Answer]
# Haskell ~~41~~ 39 chars
Works with the full set of positive and negative integers
```
f n=sum[sum$1:[-2|n<0]|i<-[3,6..abs n]]
```
First creates a list 1's or (-1)'s (depending on the sign of the input) for every third integer from 0 up until the input `n`. `abs(n)` for negative numbers inclusive.
e.g `n=8 -> [0,3,6]`
It then returns the sum of this list.
[Answer]
# [Python 3](https://docs.python.org/3/), 72 bytes
```
f=lambda x:x and s(x>>1,f(x>>1))
s=lambda x,y:y and s(x^y,(~x&y)<<1)or x
```
[Try it online!](https://tio.run/##PYwxCsMwDAB3v0JoKBYIgjF0MEmeUnBI3QpaJTgZ7KVfd0KhXe6W49a6Pxf1raXhFd/THKGEAlFn2GwZR8fpKyKz/QOuof6SW2X7KZdKfe9oyVBaOikgCjnq427dlYIBWLPoboWxAw8DnlshRossnWckJNMO "Python 3 – Try It Online")
A bitwise solution consisting of two recursive functions, one to calculate third, the other to subtract. Because multiplying and dividing by 2 is easy to do bitwise, we can use the fact:  
\$X/3=X/2-(X/2)/3\$  
to recursively find the third.
It does produce some weird rounding patterns for non-multiples of three. 
```
0 -> 0 (0)
1 -> 0 (0.333...)
2 -> 1 (0.666...)
3 -> 1 (1)
4 -> 1 (1.333...)
5 -> 1 (1.666...)
6 -> 2 (2)
7 -> 2 (2.333...)
8 -> 3 (2.666...)
9 -> 3 (3)
10 -> 4 (3.333...)
11 -> 4 (3.666...)
12 -> 4 (4)
13 -> 4 (4.333...)
14 -> 5 (4.666...)
15 -> 5 (5)
```
[Answer]
# Clojure, 87; works with negatives; based on lazyseqs
```
(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))
```
Ungolfed:
```
(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))
```
]