Printing difference of adjacent numbers without using array

Question

I recently found a C puzzle to write a program to read a set of integers x₀, x₁, x₂, ……. till a -1 is entered as input..

After reading the -1, the program should print the difference between each adjacent numbers. Ie, x₁-x₀, x₂-x₁, x₃-x₂,…..

eg: Input:
1 2 4 7 11 -1

Output
1 2 3 4

The output is the result of (2-1), (4-2), (7-4), (11-7)

The problem is that the program shouldn’t be using an array. Even the dynamically allocated arrays won’t do.

I tried a lot and this is my what I’ve come with

#include<stdio.h>

int a, b;
int fn()
{
    int r=b-a;
    a=b;
    scanf("%d", &b);
    if(b!=-1)
    {
        printf("%d ", fn());
    }
    return r;
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d ", fn() );
    return 0;
}

The above program uses a recursive function but in this method, since it is like a stack, the value that was calculated last is being printed first instead of the value that was calculated first being printed first.

ie, output for the same input as above is: 4 3 2 1 instead of 1 2 3 4

Is there a way to save the values taken from this call stack (please correct me if I’m not using the right terms) and push them again to stack so that while retrieving the first calculated value will now be the first to be popped?

Eg: I got the values 4, 3, 2 & 1 with fn() because it was like this on stack before 4 was popped:

4
3
2
1

Suppose I pop all elements from the stack and push them to another stack in the order in which they were popped. Then the new stack would be

1
2
3
4

(ie, 4 got popped and pushed first (& hence ended up in bottom), then 3 got popped & pushed and so on.)

If this could be done, we could just pop elements from the new stack and display them in the order in which they are popped.

Note: The stack that I'm referring to is the call stack & not an explicitly created stack (which would probably need array).

Or maybe there’s a simpler way?

EDIT: I need the inputting and outputting phases to be separate and not interleaved. No output should be displayed before the end of input is signaled with the -1.

EDIT: The program can't use files to store the input to be read back later.

Answer 1

Is there a way to save the values taken from this call stack ... and push them again to stack so that while retrieving the first calculated value will now be the first to be popped?

Recurse each time a number is read (except -1).

Create a linked list made up of variables in previous recursion.

No arrays used except for printf() format.

A little more work needed to avoid a space after the last printed int.

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

typedef struct list {
  const struct list *prev;
  int i;
} list;

void print_list(const list *previous) {
  if (previous && previous->prev) {
    print_list(previous->prev);
    printf("%d ", previous->i - previous->prev->i);
  }
}

void JSfoo(const list *previous) {
  list node = { previous, 0 };
  int cnt = scanf("%d", &node.i);
  if (cnt == 1 && node.i != -1) {
    JSfoo(&node);
  } else {
    print_list(previous);
    puts("");
  }
}

int main(void) {
  JSfoo(NULL);
  return 0;
}

Output (not interleaved)

1 2 4 7 11 -1
1 2 3 4 

---

An alternative would maintain a queue to negate the need to recursively print. Same output.

The below uses a circular queue. Notice only 1 next pointer needed. The queue handle needs to only point to the end of the queue. No need for pointers to the head and tail. Insertion is O(1).

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

typedef struct que {
  struct que *next;
  int i;
} que;

// Pass in the tail of the queue and return the updated tail
// `tail` points to the head.  (Circular queue)
que *que_append(que *tail, que *node) {
  if (tail) {
    node->next = tail->next;
    tail->next = node;
  } else {
    node->next = node;
  }
  return node;
}

void JSfoo(que *tail) {
  que node;
  int cnt = scanf("%d", &node.i);
  if (cnt == 1 && node.i != -1) {
    tail = que_append(tail, &node);
    JSfoo(tail);
  } else if (tail) {
    que *head = tail->next;
    while (head != tail) {
      printf("%d ", head->next->i - head->i);
      head = head->next;
    }
    puts("");
  }
}

Answer 2

Do you expect the program to stop taking any more input chars from user immediately after entering "-1" and followed by print of diff seq out?

If not, that is if you allow user to input more chars after "-1", to be ignored by your program till a newline is entered, and at that point, your program can print the diff sequence out. Then you can use the following snippet:

unsigned int x, y;
while( scanf("%d",&x)==1 && x != -1 && scanf("%d",&y)==1 && y != -1 )
    printf("%d ",y-x);
printf("\n");

EDIT: thanks @JoëlHecht for pointing out error in the above code, i misread the desired output spec, the following code should fix it:

int x, y = -1;
while( scanf("%d",&x)==1 && x != -1 ) {
    if( y != -1 ) printf("%d ",x-y);
    y = x;
}
printf("\n");