Need a faster program (time limit exceed)

[Oriol Serrabassa]

Make a program that prints 1 if there is a permutation or 0 if there is not. The first number of the input tells you how long the sequence is.

Example:
5 1 2 3 4 5 (Output = 1)
5 5 3 1 2 4 (Output = 1)
5 4 3 2 1 5 (Output = 1)
5 5 1 3 5 1 (Output = 0)
1 1 (Output = 1)
1 0 (Output = 0)
2 1 2 (Output = 1)
2 2 1 (Output = 1)
2 2 -2 (Output = 0)
2 3 1 (Output = 0)
10 2 2 2 3 4 6 7 9 10 10 (Output = 0)

#include <iostream>
#include <vector>
using namespace std;

void permutation (vector <int> no_repeat, int sequence_size) {
	bool loop = true;
	for (int j = 0; j < sequence_size and loop; ++j) {
		if (no_repeat [j] <= 0 or no_repeat [j] > sequence_size) {
			cout << "0" << endl;
			loop = false;
		}
		else {			
			bool different = true;
			bool loop2 = true;
			int substraction = 1;
			while (sequence_size - substraction >= 0 and loop2) {
				if (sequence_size - substraction == j) different = false;				
				if (no_repeat [sequence_size - substraction] == no_repeat [j] and different) loop2 = false;
				if (not different) different = true;
				++substraction;
			}
			if (not loop2) {
				cout << "0" << endl;
				loop = false;
			}
		}
	}
	if (loop) cout << "1" << endl;
}

int main () {
	int sequence_size;
	while (cin >> sequence_size) {
		vector <int> no_repeat (sequence_size);
		for (int i = 0; i < sequence_size; ++i) {
			cin >> no_repeat [i];
		}
		permutation (no_repeat, sequence_size);
	}
}

Do not know how to improve my code, I need some advice, thanks.

[JLBorges]

O(N):

#include <iostream>
#include <vector>

int main() {

    std::size_t sequence_size ;
    std::cin >> sequence_size ;

    std::vector<int> already_seen(sequence_size+1) ; // max valid position is sequence_size

    for( std::size_t i = 0; i < sequence_size; ++i ) {

        std::size_t number ;

        if( std::cin >> number && // successful input
            number > 0 && number <= sequence_size && // number is in [ 1, sequence_size ]
            already_seen[number] == 0 ) // this number was not seen earlier

        {
            already_seen[number] = 1 ; // mark this number as already seen
        }

        else // input failure, number is out of range or number is repeated
        {
            std::cout << "0\n" ;
            return 1 ;
        }
    }

    std::cout << "1\n" ; // every number in [1, sequence_size ] was seen exactly once
}

[Oriol Serrabassa]

My program has to be able to read sequences and sequences until the user ends the program. Adapted your program to this specification and made some tweaks because I have to respect some rules I have been given an this is what I have now:

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int sequence_size;
	while (cin >> sequence_size) {
		vector <int> already_seen (sequence_size+1);
		bool loop = true;
		for (int i = 0; i < sequence_size and loop; ++i) {
			int number;
			if (cin >> number and number > 0 and number <= sequence_size and already_seen[number] == 0 ) already_seen[number] = 1;
			else {		
				cout << "0" << endl;
				loop = false;
			}
		}	
		if (loop) cout << "1" << endl;
	}
}

However, the output was not the one is it supposed to be;

Example (input and expected output)
5 1 2 3 4 5
5 5 3 1 2 4
5 4 3 2 1 5
5 5 1 3 5 1
1 1
1 0
2 1 2
2 2 1
2 2 -2
2 3 1
10 2 2 2 3 4 6 7 9 10 10

1
1
1
0
1
0
1
1
0
0
0

Example (input and actual output)
5 1 2 3 4 5
5 5 3 1 2 4
5 4 3 2 1 5
5 5 1 3 5 1
1 1
1 0
2 1 2
2 2 1
2 2 -2
2 3 1
10 2 2 2 3 4 6 7 9 10 10

1
1
1
0
1
1
1
1
1
0
0
0
0
0
0
0
0

Leaving this post if someone wants to help. I will look at the code later on today, since I am busy

[JLBorges]

> However, the output was not the one is it supposed to be;

Once the variable loop is set to false (the input data does not form a permutation), we need to throw the rest of the current line away. (The next set of input data would be from the next line.)

Using the count of unique numbers read from the current line as the flag:

#include <iostream>
#include <vector>
#include <limits>

int main() {

    std::size_t sequence_size ;
    std::vector<int> already_seen ;

    while( std::cin >> sequence_size && sequence_size > 0 ) {

        already_seen.clear() ;
        already_seen.resize( sequence_size+1 ) ;

        std::size_t cnt_unique_numbers = 0 ; // count of unique numbers read
        while( cnt_unique_numbers < sequence_size ) {

            std::size_t number ;

            if( std::cin >> number && // successful input
                number > 0 && number <= sequence_size && // number is in [ 1, sequence_size ]
                already_seen[number] == 0 ) { // this number was not seen earlier

                    already_seen[number] = 1 ; // mark this number as already seen
                    ++cnt_unique_numbers ;
            }

            else { // input failure, number is out of range or number is repeated

                std::cin.clear() ; // clear a possible failed state due to a badly formed line
                // extract and discard the rest of the input on this particular line
                std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' ) ;
                break ; // we are done with this line of input (break out of the while loop)
            }
        }

        // if cnt_unique_numbers == sequence_size, we have a permutation of [ 1, sequence_size ]
        std::cout << int( cnt_unique_numbers == sequence_size ) << '\n' ;
    }
}

[Oriol Serrabassa]

Okay, I got the problem accepted but I have some few questions that I would like to be answered if possible:

1. Should a C++ beginner be able to do this problem? Because at less for my case, I have not seen "stuff" you use in the code like

#include <limits>  
cin.clear()  
cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n') 

2. Is it possible to make a working program, without using the "stuff" I mentioned in point 1 plus break Like my program, but more fast and effective?

3. Is it possible to use endl instead of \n in this line
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n' ) ? Because my programming rules stricly says to use endl instead of \n. Tried to do it myself, but with the modifications I made the program didn't compile or it printed wrong outputs or it simply printed some outputs (not all sequence). If it is possible, could you give me the code line as an example, please?

[JLBorges]

> 1. Should a C++ beginner be able to do this problem?
> Because at less for my case, I have not seen "stuff" you use in the code

Yes. A beginner could assume that input would always succeed; that there is no badly formed line in the input.


> 2. Is it possible to make a working program, without using the "stuff" I mentioned in point 1

Yes, assuming that all input to the program is clean. Your earlier code, modified to continue to consume the remaining numbers in the current data set (after a non-unique number is encountered) would do.

#include <iostream>
#include <vector>
// using namespace std;

int main() {

    int sequence_size;

    while (std::cin >> sequence_size) {

        std::vector <int> already_seen (sequence_size+1);
        bool loop = true;

        // for (int i = 0; i < sequence_size and loop; ++i) {
        for (int i = 0; i < sequence_size ; ++i) { // read all the numbers till the end

            int number;

            // if (std::cin >> number and number > 0 and number <= sequence_size and already_seen[number] == 0 ) already_seen[number] = 1;
            std::cin >> number ; // assume there would be no input failure

            if (number > 0 and number <= sequence_size and already_seen[number] == 0 ) already_seen[number] = 1 ;
            // else  {
            // cout << "0" << endl;
            // loop = false;
            // }
            else loop = false ;
        }

        // if (loop) cout << "1" << endl;
        std::cout << ( loop ? "1\n" : "0\n" ) ;
    }
}

> 3. Is it possible to use endl instead of \n in this line
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n' )

No. std::endl is an output manipulator; it is a function.
http://www.cplusplus.com/reference/ostream/endl/

The type of the second parameter of std::cin.ignore() is int - the argument must be an int that either holds the value of a character or is EOF.
http://www.cplusplus.com/reference/istream/istream/ignore/


> my programming rules stricly says to use endl instead of \n.

I presume that these 'programming rules' were framed by your teacher. Most career teachers who 'teach' C++ are people who have never done any real-life programming in C++.

CppCoreGuidelines:

Avoid endl

Reason
The endl manipulator is mostly equivalent to '\n' and "\n"; as most commonly used it simply slows down output by doing redundant flush()s. This slowdown can be significant compared to printf-style output.

Example

cout << "Hello, World!" << endl;    // two output operations and a flush
cout << "Hello, World!\n";          // one output operation and no flush 

Note
For cin/cout (and equivalent) interaction, there is no reason to flush; that's done automatically. For writing to a file, there is rarely a need to flush.

Apart from the (occasionally important) issue of performance, the choice between '\n' and endl is almost completely aesthetic.

https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rio-endl

[Oriol Serrabassa]

Okay one last question: What is this and what does it do?

std::cout << ( loop ? "1\n" : "0\n" )

I am able to guess that it checks if loop is true or false and outputs 1 or 0 and ends line depending the value of loop, but how does this actually work?

I replaced this line with this two instead so I can understand the code better:

if (loop) cout << "1" << endl;
else cout << "0" << endl;

The full operational program adapted to my programming style is the following:

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int sequence_size;
	while (cin >> sequence_size) {
		vector <int> already_seen (sequence_size+1);
		bool loop = true;
		for (int i = 0; i < sequence_size; ++i) {
			int number;
			cin >> number;
			if (number > 0 and number <= sequence_size and already_seen[number] == 0) already_seen[number] = 1;
			else loop = false ;
		}
		if (loop) cout << "1" << endl;
		else cout << "0" << endl;
	}
}

I read what you said about \n and endl, but I have to respect the programming rules I have been given and use endl but I will keep in mind \n.

[JLBorges]

> What is this and what does it do? std::cout << ( loop ? "1\n" : "0\n" )
> how does this actually work?

?: is the conditional operator See: https://msdn.microsoft.com/en-us/library/e4213hs1.aspx

We could also write: std::cout << int(loop) << '\n' ;
When a value of type bool is converted to a value of type int, false becomes zero and true becomes one.

[Oriol Serrabassa]

Thanks for all