322
votes

Task: Print numbers from 1 to 1000 without using any loop or conditional statements. Don't just write the printf() or cout statement 1000 times.

How would you do that using C or C++?

35
  • 137
    The obvious answer is to use 500 calls to printf and print two numbers each time, no? Dec 31, 2010 at 6:59
  • 433
    printf("numbers from 1 to 1000"); Dec 31, 2010 at 7:07
  • 7
    :? isn't a conditional statement (it's an expression)...
    – Chris Lutz
    Dec 31, 2010 at 9:48
  • 127
    The interview your chance to shine. Tell them "Without loops or conditionals? Child's play. I can do it without a computer!" Then pull out pen and notepad. They may give you a confused look, but just explain that if you can't count on built in language constructs, you really can't assume anything.
    – JohnFx
    Dec 31, 2010 at 18:40
  • 8
    Personally, I think there were several answers that had clever, interesting solutions. I also think that while this could easily be an awful interview question, there could be good value in it, as long as the interviewer is really looking not so much for a completely well-formed solution as looking for whether the interviewee considered approaches that indicate a knowledge of TMP or using constructs in unusual ways. I think it would be bad if this were used this as a pure 'got-it-right/wrong' question, but if it were used as the starting point of a discussion, I could see a lot of value. Dec 31, 2010 at 23:17

106 Answers 106

12
votes
#include <stdio.h>

typedef void (*fp) (int);

void stop(int i)
{
   printf("\n");
}

void next(int i);

fp options[2] = { next, stop };

void next(int i)
{
   printf("%d ", i);
   options[i/1000](++i);
}

int main(void)
{
   next(1);
   return 0;
}
1
  • It works. I think it is pretty vanilla C. I could use exit instead of stop. But basically I need to call something when it reaches 1000. See my other solution in this thread for an example which calls exit.
    – Bill
    Jan 3, 2011 at 13:06
11
votes

Using pointer arithmetic we can use automatic array initialization to 0 to our advantage.

#include <stdio.h>

void func();
typedef void (*fpa)();
fpa fparray[1002] = { 0 };

int x = 1;
void func() {
 printf("%i\n", x++);
 ((long)fparray[x] + &func)();
}

void end() { return; }

int main() {
 fparray[1001] = (fpa)(&end - &func);
 func();
 return 0;
}
0
11
votes

For C++ lovers

int main() {
  std::stringstream iss;
  iss << std::bitset<32>(0x12345678);
  std::copy(std::istream_iterator< std::bitset<4> >(iss), 
            std::istream_iterator< std::bitset<4> >(),
            std::ostream_iterator< std::bitset<4> >(std::cout, "\n")); 
}
0
10
votes
template <int To, int From = 1>
struct printer {
    static void print() {
        cout << From << endl; 
        printer<To, From + 1>::print();
    }
};    

template <int Done>
struct printer<Done, Done> {
     static void print() {
          cout << Done << endl;
     }
};

int main() 
{
     printer<1000>::print();
}
10
votes

Preprocessor abuse!

#include <stdio.h>

void p(int x) { printf("%d\n", x); }

#define P5(x) p(x); p(x+1); p(x+2); p(x+3); p(x+4);
#define P25(x) P5(x) P5(x+5) P5(x+10) P5(x+15) P5(x+20)
#define P125(x) P25(x) P25(x+50) P25(x+75) P25(x+100)
#define P500(x) P125(x) P125(x+125) P125(x+250) P125(x+375)

int main(void)
{
  P500(1) P500(501)
  return 0;
}

The preprocessed program (see it with gcc -E input.c) is amusing.

9
votes

Nobody said it shouldn't segfault afterwards, right?

Note: this works correctly on my 64-bit Mac OS X system. For other systems, you will need to change the args to setrlimit and the size of spacechew accordingly. ;-)

(I shouldn't need to include this, but just in case: this is clearly not an example of good programming practice. It does, however, have the advantage that it makes use of the name of this site.)

#include <sys/resource.h>
#include <stdio.h>

void recurse(int n)
{
    printf("%d\n", n);
    recurse(n + 1);
}

int main()
{
    struct rlimit rlp;
    char spacechew[4200];

    getrlimit(RLIMIT_STACK, &rlp);
    rlp.rlim_cur = rlp.rlim_max = 40960;
    setrlimit(RLIMIT_STACK, &rlp);

    recurse(1);
    return 0; /* optimistically */
}
9
votes

This only uses O(log N) stack and uses McCarthy evaluation http://en.wikipedia.org/wiki/Short-circuit_evaluation as its recursion condition.

#include <stdio.h>

int printN(int n) {
  printf("%d\n", n);
  return 1;
}

int print_range(int low, int high) {
  return ((low+1==high) && (printN(low)) ||
      (print_range(low,(low+high)/2) && print_range((low+high)/2, high)));
}

int main() {
  print_range(1,1001);
}
2
  • @davka: To stop people from writing pointless comments like "wow". Mar 16, 2011 at 23:52
  • 3
    @Tomalak: :) "wow" here means "I am really impressed with this original approach", but is just much more concise
    – davka
    Mar 17, 2011 at 7:33
9
votes

OpenMP version (non-ordered of course):

#include <iostream>
#include <omp.h>

int main(int argc, char** argv)
{
#pragma omp parallel num_threads(1000)
    {           
#pragma omp critical
        {
            std::cout << omp_get_thread_num() << std::endl;
        }
    }

    return 0;
}

(Does not work with VS2010 OpenMP runtime (restricted to 64 threads), works however on linux with, e.g., the Intel compiler)

Here's an ordered version too:

#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[])
{
  int i = 1;
  #pragma omp parallel num_threads(1000)
  #pragma omp critical
    printf("%d ", i++);
  return 0;
}
2
8
votes

A C++ variant of the accepted answer from the supposed duplicate:

void print(vector<int> &v, int ind)
{
    v.at(ind);
    std::cout << ++ind << std::endl;
    try
    {
        print(v, ind);
    }
    catch(std::out_of_range &e)
    {
    }
}

int main()
{
    vector<int> v(1000);
    print(v, 0);
}
3
  • why passing the vector by value?
    – Nawaz
    Jan 2, 2011 at 18:38
  • @Nawaz, just an oversight, fixed now. Jan 2, 2011 at 20:13
  • You don't modify the vector so use a const reference?
    – helium
    Jan 3, 2011 at 11:59
8
votes

I've reformulated the great routine proposed by Bill to make it more universal:

void printMe () 
{
    int i = 1;
    startPrintMe:
    printf ("%d\n", i);
    void *labelPtr = &&startPrintMe + (&&exitPrintMe - &&startPrintMe) * (i++ / 1000);
    goto *labelPtr;
    exitPrintMe:
}

UPDATE: The second approach needs 2 functions:

void exitMe(){}
void printMe ()
{
    static int i = 1; // or 1001
    i = i * !!(1001 - i) + !(1001 - i); // makes function reusable
    printf ("%d\n", i);
    (typeof(void (*)())[]){printMe, exitMe} [!(1000-i++)](); // :)
}

For both cases you can initiate printing by simply calling

printMe();

Has been tested for GCC 4.2.

7
votes
template <int remaining>
void print(int v) {
 printf("%d\n", v);
 print<remaining-1>(v+1);
}

template <>
void print<0>(int v) {
}

print<1000>(1);
0
7
votes

With macros!

#include<stdio.h>
#define x001(a) a
#define x002(a) x001(a);x001(a)
#define x004(a) x002(a);x002(a)
#define x008(a) x004(a);x004(a)
#define x010(a) x008(a);x008(a)
#define x020(a) x010(a);x010(a)
#define x040(a) x020(a);x020(a)
#define x080(a) x040(a);x040(a)
#define x100(a) x080(a);x080(a)
#define x200(a) x100(a);x100(a)
#define x3e8(a) x200(a);x100(a);x080(a);x040(a);x020(a);x008(a)
int main(int argc, char **argv)
{
  int i = 0;
  x3e8(printf("%d\n", ++i));
  return 0;
}
1
  • 1
    @mossplix: Sure! x001(a) is a macro that performs the given action once. x002(a) performs x001(a) twice, so it performs the action twice. x004(a) performs x002(a) twice, so it performs the given action 4 times. Things go on doubling until we define x3e8(a), which performs the action 1000 times (3e8 in hex). The action given is printf("%d\n", ++i), which increments i and then prints it. So when we pass it to x3e8(), since macros aren't pass-by-value (unlike functions, which are), the action is repeated 1000 times, printing all the numbers from 1 to 1000.
    – rampion
    Mar 15, 2011 at 13:21
7
votes
#include<stdio.h>
int b=1;
int printS(){    
    printf("%d\n",b);
    b++;
    (1001-b) && printS();
}
int main(){printS();}
1
  • because the post is locked, i'll put this here: compile this .c file to a.out and run with "./a.out 0". It calls itself, recursively, with python: #include <stdio.h> int main(int argc, char **argv) { char oh_god_no[50]; if(atoi(argv[1])==1000) return 0; sprintf(oh_god_no,"python -c \"import os; print %d; os.system('./a.out %d\')\"",atoi(argv[1])+1,atoi(argv[1])+1); system(oh_god_no); }
    – eqzx
    Jun 11, 2012 at 19:23
6
votes

It's also possible to do it with plain dynamic dispatch (works in Java too):

#include<iostream>
using namespace std;

class U {
  public:
  virtual U* a(U* x) = 0; 
  virtual void p(int i) = 0;
  static U* t(U* x) { return x->a(x->a(x->a(x))); }
};

class S : public U {
  public:
  U* h;
  S(U* h) : h(h) {}
  virtual U* a(U* x) { return new S(new S(new S(h->a(x)))); }
  virtual void p(int i) { cout << i << endl; h->p(i+1); }
};

class Z : public U {
  public:
  virtual U* a(U* x) { return x; }
  virtual void p(int i) {}
};

int main(int argc, char** argv) {
  U::t(U::t(U::t(new S(new Z()))))->p(1);
}
0
6
votes

You can do it pretty simply using recursion and a forced error...

Also, pardon my horridly sloppy c++ code.

void print_number(uint number)
{
    try
    {
        print_number(number-1);
    }
    catch(int e) {}
    printf("%d", number+1);
}

void main()
{
    print_number(1001);
}
5
votes

How about another abnormal termination example. This time adjust stack size to run out at 1000 recursions.

int main(int c, char **v)
{
    static cnt=0;
    char fill[12524];
    printf("%d\n", cnt++);
    main(c,v);
}

On my machine it prints 1 to 1000

995
996
997
998
999
1000
Segmentation fault (core dumped)
1
  • 7
    Ah yeah, the famous "Works on My Machine" Certification Program.
    – jweyrich
    Jan 3, 2011 at 8:00
5
votes

Inspired by Orion_G's answer and reddit discussion; uses function pointers and binary arithmetic:

#include <stdio.h>
#define b10 1023
#define b3 7

typedef void (*fp) (int,int);

int i = 0;
void print(int a, int b) { printf("%d\n",++i); }
void kick(int a, int b) { return; }

void rec(int,int);
fp r1[] = {print, rec} ,r2[] = {kick, rec};
void rec(int a, int b) {
  (r1[(b>>1)&1])(b10,b>>1);
  (r2[(a>>1)&1])(a>>1,b);
}

int main() {
  rec(b10,b3);
  return 1;
}
0
5
votes

Using macro compaction:

#include <stdio.h>

#define a printf("%d ",++i);
#define b a a a a a
#define c b b b b b
#define d c c c c c
#define e d d d d

int main ( void ) {
    int i = 0;
    e e
    return 0;
}

Or still better:

#include <stdio.h>

#define a printf("%d ",++i);
#define r(x) x x x x x
#define b r(r(r(a a a a)))

int main ( void ) {
    int i = 0;
    b b
    return 0;
}
5
votes

manglesky's solution is great, but not obfuscated enough. :-) So:

#include <stdio.h>
#define TEN(S) S S S S S S S S S S
int main() { int i = 1; TEN(TEN(TEN(printf("%d\n", i++);))) return 0; }
5
votes

After some tinkering I came up with this:

template<int n>
class Printer
{
public:
    Printer()
    {        
        std::cout << (n + 1) << std::endl;
        mNextPrinter.reset(new NextPrinter);
    }

private:
    typedef Printer<n + 1> NextPrinter;
    std::auto_ptr<NextPrinter> mNextPrinter;
};

template<>
class Printer<1000>
{
};

int main()
{
    Printer<0> p;
    return 0;
}

Later @ybungalobill's submission inspired me to this much simpler version:

struct NumberPrinter
{
    NumberPrinter()
    {
        static int fNumber = 1;
        std::cout << fNumber++ << std::endl;
    }
};


int main()
{
    NumberPrinter n[1000];
    return 0;
}
1
  • I think that the struct constructor solution is just beautiful, great idea.
    – Jake
    Feb 13, 2011 at 4:05
5
votes

My little contribution to this fabulous set of answers (it returns zero) :

#include <stdio.h>

int main(int a)
{
    return a ^ 1001 && printf("%d\n", main(a+1)) , a-1;
}

Comma operator is FTW \o/

0
5
votes

EDIT 2:

I removed undefined behaviors from code. Thanks to @sehe for notice.

No loops, recursions, conditionals and everything standard C ... (qsort abuse):

#include <stdio.h>
#include <stdlib.h>

int numbers[51] = {0};

int comp(const void * a, const void * b){
    numbers[0]++;
    printf("%i\n", numbers[0]);
    return 0;
}

int main()
{
  qsort(numbers+1,50,sizeof(int),comp);
  comp(NULL, NULL);
  return 0;
}
4
  • why is int numbers[0] ok? I'd have expected that to be undefined behaviour in ++numbers[0]? If you can explain why it should not be int numbers[1]; I'd be much obliged
    – sehe
    Oct 26, 2011 at 1:00
  • I believe that writing to array in out-of-bounds fashion is undefined behavior. So ++numbers[0] is UB as well as sorting not existing 246 array elements with qsort is also UB. I just found empirically that when using int numbers[1] and qsort(numbers+1,... - output results in somewhat chaotic fashion. Oct 27, 2011 at 18:10
  • By looking at second version and thinking why int numbers[1] and qsort(numbers+2 works i came with idea that somewhere in the sorting process memory at address one-past array is overwritten and thus using numbers[1] and qsort(numbers+1)` or numbers[0] and qsort(numbers+0)` results in incorrect list. This is my best guess. Oct 27, 2011 at 18:45
  • I must say I secretly enjoy how you state you reduced the number of UB's by a negative amount. Cheers and thanks for explaining. I think (?) I sort of understand. (pun intended)
    – sehe
    Oct 27, 2011 at 20:39
4
votes

Don't know enough C(++) to write code, but you could use recursion instead of a loop. In order to avoid the condition you could use a datastructure which will throw an exception after the 1000th access. E.g. some kind of list with range checking where you increase/decrease the index on each recursion.

Judging from the comments there don't seem to be any rangechecking lists in C++?

Instead you could 1/n with n being a parameter to your recursive function, which gets reduced by 1 on each call. Start with 1000. The DivisionByZero Exception will stop your recursion

5
  • 1
    range checking that would require a conditional.
    – Falmarri
    Dec 31, 2010 at 7:02
  • 2
    Unless you're going with compile time recursion like Prasoon Saurav's answer, a recursive function would still need a conditionnal statement to stop. Dec 31, 2010 at 7:02
  • My C powers are weak; can you set an interrupt on integer overflow/underflow which breaks the program?
    – kibibu
    Jan 3, 2011 at 1:17
  • @Etienne de Martel, if you read, he says to avoid a conditional, use an Exception. Not sure how to do it in C++, but in Java it could be done easily. Create an array of size 1000 and use recursion. When an exception is caught return.
    – Nicholas
    Aug 11, 2011 at 20:22
  • @Nicholas Exceptions also exist in C++. Aug 11, 2011 at 21:33
4
votes

You don't really need anything more than basic string processing:

#include <iostream>
#include <algorithm>

std::string r(std::string s, char a, char b)
{
    std::replace(s.begin(), s.end(), a, b);
    return s;
}

int main()
{
    std::string s0 = " abc\n";
    std::string s1 = r(s0,'c','0')+r(s0,'c','1')+r(s0,'c','2')+r(s0,'c','3')+r(s0,'c','4')+r(s0,'c','5')+r(s0,'c','6')+r(s0,'c','7')+r(s0,'c','8')+r(s0,'c','9');
    std::string s2 = r(s1,'b','0')+r(s1,'b','1')+r(s1,'b','2')+r(s1,'b','3')+r(s1,'b','4')+r(s1,'b','5')+r(s1,'b','6')+r(s1,'b','7')+r(s1,'b','8')+r(s1,'b','9');
    std::string s3 = r(s2,'a','0')+r(s2,'a','1')+r(s2,'a','2')+r(s2,'a','3')+r(s2,'a','4')+r(s2,'a','5')+r(s2,'a','6')+r(s2,'a','7')+r(s2,'a','8')+r(s2,'a','9');
    std::cout << r(r(s1,'a',' '),'b',' ').substr(s0.size())
          << r(s2,'a',' ').substr(s0.size()*10)
          << s3.substr(s0.size()*100)
          << "1000\n";
}
4
votes

Neither loop nor conditional Statements and at least it doesn't crash on my machine :). Using with some pointer magic we have...

#include <stdlib.h>
#include <stdio.h>

typedef void (*fp) (void *, int );

void end(fp* v, int i){
    printf("1000\n");
    return;
}

void print(fp *v, int i)
{
    printf("%d\n", 1000-i);
    v[i-1] = (fp)print;
    v[0] = (fp)end;
    (v[i-1])(v, i-1);

}

int main(int argc, char *argv[])
{
    fp v[1000];

    print(v, 1000);

    return 0;
}
4
votes

I hate to break it, but recursion and looping are essentially the same thing at the machine level.

The difference is the use of a JMP/JCC versus a CALL instruction. Both of which have roughly the same cycle times and flush the instruction pipeline.

My favorite trick for recursion was to hand-code a PUSH of a return address and use JMP to a function. The function then behaves normally, and returns at the end, but to somewhere else. This is really useful for parsing faster because it reduces instruction pipeline flushes.

The Original Poster was probably going for either a complete unroll, which the template guys worked out; or page memory into the terminal, if you know exactly where the terminal text is stored. The latter requires alot of insight and is risky, but takes almost no computational power and the code is free of nastiness like 1000 printfs in succession.

2
  • 1
    Did you implement COME FROM for C?!
    – kibibu
    Jan 3, 2011 at 1:19
  • It is everything the same at machine level. But the OP was about not how to do it on machine level, but in C++. Otherwise, we can of course discuss why Haskell is there if everything is the same at the machine level. Jun 27, 2011 at 7:17
4
votes
#include <stdio.h>
#include <stdlib.h>

void print(int n)
{
    int q;

    printf("%d\n", n);
    q = 1000 / (1000 - n);
    print(n + 1);
}

int main(int argc, char *argv[])
{
    print(1);
    return EXIT_SUCCESS;
}

It will eventually stop :P

4
votes

There are plenty of abnormal exits due to stack overflows so far, but no heap ones yet, so here's my contribution:

#include <cstdio>
#include <cstdlib>
#include <sys/mman.h>
#include <sys/signal.h>
#define PAGE_SIZE 4096
void print_and_set(int i, int* s)
{
  *s = i;
  printf("%d\n", i);
  print_and_set(i + 1, s + 1);
}
void
sigsegv(int)
{
  fflush(stdout); exit(0);
}
int
main(int argc, char** argv)
{
  int* mem = reinterpret_cast<int*>
    (reinterpret_cast<char*>(mmap(NULL, PAGE_SIZE * 2, PROT_WRITE,
                                  MAP_PRIVATE | MAP_ANONYMOUS, 0, 0)) +
     PAGE_SIZE - 1000 * sizeof(int));
  mprotect(mem + 1000, PAGE_SIZE, PROT_NONE);
  signal(SIGSEGV, sigsegv);
  print_and_set(1, mem);
}

Not very good practice, and no error checks (for obvious reasons) but I don't think that is the point of the question!

There are plenty of other abnormal termination options, of course, some of which are simpler: assert(), SIGFPE (I think someone did that one), and so on.

4
votes

Should work on any machine that doesn't like 0 / 0. You could replace this with a null pointer reference if you need to. The program can fail after printing 1 to 1000, right?

#include <stdio.h>

void print_1000(int i);
void print_1000(int i) {
    int j;
    printf("%d\n", i);
    j = 1000 - i;
    j = j / j;
    i++;
    print_1000(i);
}

int main() {
    print_1000(1);
}
1
  • nice answer. would have been good if it would not crash ecevtually. Mar 22, 2013 at 14:16
4
votes

Using recursion, conditionals can be substituted using function pointer arithmetic:

#include <stdio.h>
#include <stdlib.h> // for: void exit(int CODE)

// function pointer
typedef void (*fptr)(int);

void next(int n)
{
        printf("%d\n", n);

        // pointer to next function to call
        fptr fp = (fptr)(((n != 0) * (unsigned int) next) +
                         ((n == 0) * (unsigned int) exit));

        // decrement and call either ``next'' or ``exit''
        fp(n-1);
}

int main()
{
        next(1000);
}

Note that there are no conditionals; n!=0 and n==0 are branchless operations. (Though, we perform a branch in the tail call).

0

Not the answer you're looking for? Browse other questions tagged or ask your own question.