Help Me Solve This Linear Search Problem

[reinattwijaya]

Okay, so i am a beginner and i am trying to learn solving some problem then i saw this problem on https://training.ia-toki.org/problemsets/35/problems/183/. Well i already did it on eclipse but it seems that the answer still incorrect according to the site. Please tell me why it is wrong :

#include <iostream>
#include <math.h>

using namespace std;

int main() {

int a, b;

int c = -1;

cin >> a >> b;

if (pow(10, 6) < a) {
a = pow(10, 6);
}

if (1 > a) {
a = 1;
}

if (b > pow(10, 5)) {
b = pow(10, 5);
}

if (0 > b) {
b = 0;
}

/* cout << "Value 1 : " << a << endl;
cout << "Value 2 : " << b << endl;*/

int array[a];

for (int x = 0; x < a; x++) {

cin >> array[x];
if (array[x] > pow(10, 5)) {
array[x] = pow(10, 5);
}
if (0 > array[x]) {
array[x] = 0;
}

}

for (int x = 0; x < a + 1; x++) {

if (array[x] == b) {
cout << x;
break;
}
if (x == a) {
cout << c << endl;
}

}

return 0;
}

[Chervil]

As I understand it, you have some example input data like this:

5 30
10
4
15
30
30

5 is the number of integers to follow.
30 is the number to search for.
The first occurrence of value 30 is found in element 3, so the output is 3

  0  1  2  3  4
 10  4 15 30 30

That's fairly straightforward.

I don't understand what the code is doing. What has the pow() function to do with any of this? I don't see any purpose.



If you are later going to use a binary search too, then you will need to store the values in an array or std::vector. That is not necessary for the current problem, you can do the search as the data is being read from the input cin.


Finally - if your program is judged by an automated system, then you have to ensure that the output is exactly as expected - no more, no less. Probably your code has additional cout statements which create extra unwanted output.

[reinattwijaya]

okay, I understand about the problem, but when i ran my program it seems to work just fine and bring the example on the site the exact number. It doesn't really give that much of an output explanation, so do i have to delete all of the input before showing the output like the one at the site?

By the way the pow () function is for the maximum and minimum value on the bottom of the explanation but i don't really like to write 1000000, it can confuse me with that many numbers of zeroes so i decided to go with the pow.
Oh yeah, thanks for the explanation i really appreciate it

[Chervil]

so do i have to delete all of the input before showing the output like the one at the site?

I think you just need to remove the cout statements except for the one which gives the final result. Oops - I may have misread the code - there are some lines enclosed in /* */ which I may have not noticed yesterday.

By the way the pow () function is for the maximum and minimum value on the bottom of the explanation but i don't really like to write 1000000, it can confuse me with that many numbers of zeroes so i decided to go with the pow.

Yes, I eventually realised it was something like that.

However, I think this is a misunderstanding. Those values,

Batasan

1 ≤ N ≤ 10⁶
0 ≤ M, D ≤ 10⁵

are there for your guidance when designing your program.

For example the value 10⁵ is too large to fit in a 16-bit integer, but will easily fit into a 32-bit integer. This gives you the ability to choose what type of variables to use. int will be ok.

Also, if you were considering using an array of such variables, you know there could be up to 10⁶ elements in the array. Is such an array feasible? Yes, since each 32-bit integer uses 4 bytes, an array of such ints will use about 4MB of memory, which is perfectly feasible. However it is too large to fit on the stack, you would need to use dynamic memory allocation - I'd use a std::vector but you could also use new / delete too for the dynamic array.

All of those are design criteria, you don't need to write code to test the values, that would be pointless, since the instructions are telling you that the values are already guaranteed to be within those constraints.

As an aside, if you did need to write a value of 1000000 without risk of confusion over the number of zeros, instead of using the pow() function, simply use scientific notation. 1E6 or 1e6 instead of pow(10,6).

[Chervil]

There is an error in the program if you are using standard C++.

int array[a];

this is not allowed in ISO standard C++, because the value of a must be a compile-time constant, but it isn't known until run time. Hence you would use dynamic allocation

    int * array = new int[a];

and when finished using the array,

    delete [] array;

just before return 0; at the end of main()

[Chervil]

Another comment.
This loop is flawed in more than one way:

for (int x = 0; x < a + 1; x++) {

    if (array[x] == b) {
        cout << x;
        break;
    }
    if (x == a) {
        cout << c << endl;
    }

}

The one which concerns me is that the loop executes one time too many. It will be testing the value of array[x] when x is equal to a. That is an out of bounds array access. You could fix it by switching the order of events, so that line is never executed when x == a.

for (int x = 0; x < a + 1; x++) {

    if (x == a) {
        cout << c << endl;
        break;
    }

    if (array[x] == b) {
        cout << x;
        break;
    }

}

The other problem is that there are two different cout statements,

        cout << c << endl;
        cout << x;

Notice the difference? One has an endl, the other does not. The automated tester may be very choosy about which format it will accept. Try both with the endl, or both without.

Actually, I'd do it this way, so there is only one cout. Also use x < a so there is no out of bounds access

    int c = -1;
    
    for (int x = 0; x < a; x++) 
    {    
        if (array[x] == b) 
        {
            c = x;
            break;
        }
        
    }
    
    cout << c;

[reinattwijaya]

I'm sorry i couldnt reply earlier, i got a big project from my school.
I didn't think of that way to simplify my code, man you are a genius.
But well i don't know what they want here is some of the results i tried :

This simplier code get me 50 points :

#include <iostream>
#include <math.h>

using namespace std;

int main() {

int a, b;

int c = -1;

cin >> a >> b;

if (1 > a > pow(10, 6)) {
a = pow(10, 6);
}
if (0 > b > pow(10, 5)) {
b = pow(10, 5);
}
/* cout << "Value 1 : " << a << endl;
cout << "Value 2 : " << b << endl;*/

int array[a];

for (int x = 0; x < a; x++) {

cin >> array[x];
if (0 > array[x] > pow(10, 5)) {
array[x] = pow(10, 5);
}

}

for (int x = 0; x < a + 1; x++) {

if (array[x] == b) {
cout << x;
break;
}
if (x == a) {
cout << c << endl;
}

}

return 0;
}

After i added the boundaries for the input it gets 0 point :

#include <iostream>
#include <math.h>

using namespace std;

int main() {

int a, b;

int c = -1;

cin >> a >> b;

if (pow(10, 6) < a) {
a = pow(10, 6);
}

if (1 > a) {
a = 1;
}

if (b > pow(10, 5)) {
b = pow(10, 5);
}

if (0 > b) {
b = 0;
}

/* cout << "Value 1 : " << a << endl;
cout << "Value 2 : " << b << endl;*/

int array[a];

for (int x = 0; x < a; x++) {

cin >> array[x];
if (array[x] > pow(10, 5)) {
array[x] = pow(10, 5);
}
if (0 > array[x]) {
array[x] = 0;
}

}

for (int x = 0; x < a + 1; x++) {

if (array[x] == b) {
cout << x;
break;
}
if (x == a) {
cout << c << endl;
}

}

return 0;
}

From your code, i got 5 points only, i don't know what this website wants :

#include <iostream>
#include <math.h>

using namespace std;

int main() {

int a, b;

int c = -1;

cin >> a >> b;

if (pow(10, 6) < a) {
a = pow(10, 6);
}

if (1 > a) {
a = 1;
}

if (b > pow(10, 5)) {
b = pow(10, 5);
}

if (0 > b) {
b = 0;
}

/* cout << "Value 1 : " << a << endl;
cout << "Value 2 : " << b << endl;*/

int * array = new int [a];

for (int x = 0; x < a; x++) {

cin >> array[x];
if (array[x] > pow(10, 5)) {
array[x] = pow(10, 5);
}
if (0 > array[x]) {
array[x] = 0;
}

}

for (int x = 0; x < a; x++) {

if (array[x] == b) {
c = x;
break;
}
}

cout << c << endl;

delete [] array;

return 0;
}

[Chervil]

Maybe there's a problem with the way I express myself.
1. Instead of pow(10, 6) simply put 1e6.
2. The restrictions given are to help you to decide how to design the program. You don't need to write any extra code, that is a misunderstanding.

Take this second example from above:

#include <iostream>
#include <math.h>

using namespace std;

int main() {

    int a, b;

    int c = -1;

    cin >> a >> b;

    if (pow(10, 6) < a) {
        a = pow(10, 6);
    }

    if (1 > a) {
        a = 1;
    }

    if (b > pow(10, 5)) {
        b = pow(10, 5);
    }

    if (0 > b) {
        b = 0;
    }

    /* cout << "Value 1 : " << a << endl;
        cout << "Value 2 : " << b << endl;*/

    int * array = new int [a];

    for (int x = 0; x < a; x++) {

        cin >> array[x];
        if (array[x] > pow(10, 5)) {
            array[x] = pow(10, 5);
        }
        if (0 > array[x]) {
            array[x] = 0;
        }

    }

    for (int x = 0; x < a; x++) {

        if (array[x] == b) {
            c = x;
            break;
        }
    }

    cout << c << endl;

    delete [] array;

    return 0;
} 

Let's remove all the unnecessary code:

#include <iostream>
//#include <math.h>

using namespace std;

int main() {

    int a, b;

    int c = -1;

    cin >> a >> b;

//    if (pow(10, 6) < a) {
//        a = pow(10, 6);
//    }

//    if (1 > a) {
//        a = 1;
//    }

//    if (b > pow(10, 5)) {
//        b = pow(10, 5);
//    }

//    if (0 > b) {
//        b = 0;
//    }

    /* cout << "Value 1 : " << a << endl;
        cout << "Value 2 : " << b << endl;*/

    int * array = new int [a];

    for (int x = 0; x < a; x++) {

        cin >> array[x];
//        if (array[x] > pow(10, 5)) {
//            array[x] = pow(10, 5);
//        }
//        if (0 > array[x]) {
//            array[x] = 0;
//        }

    }

    for (int x = 0; x < a; x++) {

        if (array[x] == b) {
            c = x;
            break;
        }
    }

    cout << c << endl;

    delete [] array;

    return 0;
} 

Now it will look like this:

#include <iostream>

using namespace std;

int main() {

    int a, b;

    int c = -1;

    cin >> a >> b;

    int * array = new int [a];

    for (int x = 0; x < a; x++) {
        cin >> array[x];
    }

    for (int x = 0; x < a; x++) {
        if (array[x] == b) {
            c = x;
            break;
        }
    }

    cout << c << endl;

    delete [] array;

    return 0;
} 

[reinattwijaya]

sorry i was busy with my script for the last few weeks
and i tried the simplified code at the training gate
YES that's it, the answer i've been searching for
i misunderstood it XD, so the thing with the code is only simplifying the code and what you told me before was about some information for me to actually redesigning the code if i wanted to, am i right?
thank you so much for the help Chevril this has been a really wonderful time, thank you very much

[Chervil]

That's good that you got it to work.

what you told me before was about some information for me to actually redesigning the code if i wanted to, am i right?

Well, not exactly. The main thing is that the information is there to help you, it is intended to make your life easier. But anyway, that's enough from me for now for now on this, I think.

You're welcome to ask again if you have questions on your next project.