Member Avatar for marnun

This is the exercise I have in codelab. I've been going over and over, and just can't see how to do it without an array. Must be something simple that I am missing. Any suggestions?
_____
Assume you have a int variable n that has already been declared and initialized. Its value is the number of integers that need to be read in from standard input and printed out in sorted (ascending) order, each on a line by itself. Furthermore, there are no duplicates in the input and every number to be read is a non-negative value that is less than n's value.

In this exercise you may not use any array (or fancy STL collection such as a vector). You may declare a variable or two as needed. With these restrictions, read the n values and print them out as required onto standard output.
_____

  • 3 Contributors
  • 6 Replies
  • 3K Views
  • 2 Hours Discussion Span
  • Latest Post Latest Post by marnun

Dani AI

Generated

You are right to suspect a trick here. With ’s observation, notice the constraints force the input to be a permutation of 0..n-1: there are n numbers, all distinct, all in [0, n). The only set that satisfies that is exactly {0, 1, 2, ..., n-1}. So the algorithm is: read and discard the n inputs (to satisfy the I/O requirement), then print 0..n-1 in order. No array or container is needed because the sorted result is determined by the constraints, not by the input order.

Why your nested-loop attempt cannot work: you try to implement a selection-sort style pass, but without storing previously read values you cannot revisit them. The inner loop consumes additional input that you never keep, so you end up reading more than n values and losing track of candidates. Without memory, a true sorting pass is impossible unless the inputs are constrained as above.

If you want a sanity-check that still respects the "no arrays/vectors" rule and uses just a variable or two, a bitmask works for small n (e.g., n <= 64). It tracks which values you saw and then emits them in order:

unsigned long long seen = 0ULL;

// read exactly n inputs
for (int k = 0; k < n; ++k) {
    int v;
    std::cin >> v;            // assumes v in [0, n) and no duplicates
    seen |= (1ULL << v);      // mark value as seen
}

// print in ascending order
for (int v = 0; v < n; ++v) {
    if (seen & (1ULL << v)) {
        std::cout << v << '\n';
    }
}

This mirrors ’s idea of using structure to get sorted output, but keeps it to a single scalar variable. If n might exceed the word size, stick with the logic trick; the problem’s constraints are designed so you do not need any data structure at all.

Recommended Answers

All 6 Replies

Member Avatar for NathanOliver

This was alread answered here. It is a trick question.

Member Avatar for L7Sqr

Hard to say if this falls within the

... a variable or two as needed.

requirement but you can construct a binary search tree which, by it's properties, is always sorted. Printing the sorted items requires only an inorder traversal of the tree.

Member Avatar for marnun

thank you for you reply.
Nathan: That thread never came out with correct solution.

L7Sqr: I am taking introductory class to c++, and not familiar with binary search tree. there must be some simple code?!

okay, n is int, declared and initialized. values entered belong to [0;value(n)).
no duplicates. what required is to read them from standard input (which is simple 'for' loop), and print them out in ascending order (this is where i am lost).

Member Avatar for marnun

here is the code i came out with, but it's wrong somewhere:

int inpt;
for (int i=0; i<n; i++) {
    cin>>inpt;
    int small=inpt;
    for (int j=i; j<n; j++) {
        cin>>inpt;
        if (inpt<small)
            small=inpt;
    }
    cout<<small<<endl;
}
Member Avatar for NathanOliver

This is the code from the post I linked to.

#include <iostream>
using namespace std;

int main()
{
    int n = 10, inpt;

    for( int i = 0; i < n; i++ )
        cin >> inpt;

    for( int i = 0; i < n; i++ )
        cout << i << endl;

    return 0;
}

What this does is that it reads in the n number of integers. Then it displays to the console integers in the range 0 -> n-1. The problem says "there are no duplicates in the input and every number to be read is a non-negative value that is less than n's value.". Since there are no duplicates and all numbers are less than n all you need to do is display 0 to n-1.

Member Avatar for marnun

oh, thank you :-)!!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.