How to find max int value from array

Question

User inputs positive int value (number);
User prints number int values;
Need to find max value and print it.

My code is

#include <stdio.h>

int main() {
    int number;
    int max;
    int temp;

    scanf("%d", &number);
    scanf("%d", &max);

    for ( int i = 1; i < number; i++ ) {
        scanf("%d", &temp);
        if ( temp > max ) {
            max = temp;
        }
    }

    printf("%d\n", max);
    return 0;
}

This works but online test tool says i need to optimize code, because it uses too many operations. Arrays are forbidden. Can only use stdio.

Set `max` to `INT_MIN` (from ``) initially, don't input it. If you're going to ask the user for the max, there's no point in writing a program to find it, is ther? — unwind, Jun 25 '12 at 10:24
@unwind - Actually, OP uses `max` to input the *first* number, then inputs the next `number - 1` numbers in a loop. i.e. its just a weird way to write this program, but it is functionally correct. — ArjunShankar, Jun 25 '12 at 10:26
I don't think that that problem could be solved with less operations ...? — Kijewski, Jun 25 '12 at 10:30
Test tool is used in my programming classes. I can't use limits.h. I know this looks stupid, but i've been trying to solve this for last 30 hours straight. — user1479645, Jun 25 '12 at 10:37
you can shave off a line or two as suggested by @ArjunShankar but no more. You can code `0` as initial max assuming that you're expecting positive numbers only. — Salman A, Jun 25 '12 at 10:47
By using [Duff's device](http://stackoverflow.com/q/514118) you could save some comparisons in the for-loop. It'd be a bad practice, but maybe that's what you are expected to do. (?) — Kijewski, Jun 25 '12 at 10:51
Does this test tool have any documentation? What is the definition of "operation"? — unkulunkulu, Jun 25 '12 at 11:06
There's short description but its in russian, and theres no definition of "operation" — user1479645, Jun 25 '12 at 11:12

score 4 · Answer 1 · edited May 23 '17 at 12:12

By using Duff's device you could save some comparisons in the for-loop. It'd be a bad practice, but maybe that's what you are expected to do.

#include <stdio.h>

int main (void) {
    unsigned max = 0;
    unsigned length;
    scanf("%u", &length);

    unsigned temp = 0;
    unsigned iterations = (length+8-1) / 8;
    switch (length % 8) {
        case 0: do { scanf("%u", &temp); if (temp > max) max = temp;
        case 7:      scanf("%u", &temp); if (temp > max) max = temp;
        case 6:      scanf("%u", &temp); if (temp > max) max = temp;
        case 5:      scanf("%u", &temp); if (temp > max) max = temp;
        case 4:      scanf("%u", &temp); if (temp > max) max = temp;
        case 3:      scanf("%u", &temp); if (temp > max) max = temp;
        case 2:      scanf("%u", &temp); if (temp > max) max = temp;
        case 1:      scanf("%u", &temp); if (temp > max) max = temp;
                } while (--iterations > 0);
    }

    printf("%u\n", max);
    return 0;
}

I used unsigned ints, because you said you only have positive numbers. The code assumes that the sequence has at least one element.

Update 1:

Example using manual loop unrolling. That's an even worse practice than Duff's device. Maybe the testing tool you got will like it, but you should never use this code to impress a potential employer!

#include <stdio.h>

int main (void) {
    signed max = -0x80000000;
    unsigned length;
    scanf("%u", &length);

    signed temp;
    for (; length >= 8; length -= 8) {
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
    }
    if (length > 4) {
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        scanf("%d", &temp); if (temp > max) max = temp;
        length -= 4;
    }
    for (; length > 0; --length) {
        scanf("%d", &temp); if (temp > max) max = temp;
    }

    printf("%d\n", max);
    return 0;
}

Update 2:

You stated that your evaluation tool likes it if scanf is less often called, so:

#include <stdio.h>
int main (void) {
    signed max = -0x80000000;
    unsigned length;
    scanf("%u", &length);

    signed t1, t2, t3, t4, t5, t6, t7, t8;
    for (; length >= 8; length -= 8) {
        scanf("%d%d%d%d%d%d%d%d", &t1, &t2, &t3, &t4, &t5, &t6, &t7, &t8);
        if (t1 > max) max = t1;
        if (t2 > max) max = t2;
        if (t3 > max) max = t3;
        if (t4 > max) max = t4;
        if (t5 > max) max = t5;
        if (t6 > max) max = t6;
        if (t7 > max) max = t7;
        if (t8 > max) max = t8;
    }
    if (length > 4) {
        scanf("%d%d%d%d", &t1, &t2, &t3, &t4);
        if (t1 > max) max = t1;
        if (t2 > max) max = t2;
        if (t3 > max) max = t3;
        if (t4 > max) max = t4;
        length -= 4;
    }
    for (; length > 0; --length) {
        scanf("%d", &t1); if (t1 > max) max = t1;
    }

    printf("%d\n", max);
    return 0;
}

@unkulunkulu, I read it wrong, sorry. I leave the task for OP to change it back to `signed`. ;-) — Kijewski, Jun 25 '12 at 11:08
thanks for response. tool doesn't work with case-switch and do-while. Is its possible to remake this with if-else and for or i should just commit suicide? — user1479645, Jun 25 '12 at 11:55
@user1479645 now using manual [loop unrolling](http://en.wikipedia.org/wiki/Loop_unwinding). — Kijewski, Jun 25 '12 at 22:29

score 2 · Answer 2 · answered Jun 25 '12 at 10:42

2

I'd like to know what test tool says you have too many operations that isn't some code golf competition. Also, what the number of acceptable operations is and how they define 'operation'.

#include <stdio.h>

int main() {
    int numbersLeft,
        number,
        max = 0;

    scanf("%d", &numbersLeft);

    while ( numbersLeft-- ) {
        scanf("%d", &number);
        max = number > max? number: max;
    }

    printf("%d\n", max);
    return 0;
}

answered Jun 25 '12 at 10:42

SpacedMonkey

2,725
1
16
17

Sure, use INT_MIN instead of 0 – SpacedMonkey Jun 25 '12 at 10:57
That's why I asked how they define operation. Is it the number of operands the code compiles to or is it the number of instructions used to run through a list. – SpacedMonkey Jun 25 '12 at 10:58
With code i posted. Test tool says "161 operations". If set max to "-2147483647 - 1" then its "174 operations". i can't use `limits.h` – user1479645 Jun 25 '12 at 11:00
Right. We don't know what an 'operation' is here. But if anything, inputting the first number into `max` will reduce the number of 'operations', or keep it the same (as per *any* definition of operation). I like your answer, but I really would like it if you do this too. – ArjunShankar Jun 25 '12 at 11:01
tool doesn't understand DO-WHILE, WHILE, ternary operations. – user1479645 Jun 25 '12 at 11:09
Tool is broken like ArjunShankar said. Unless you can find a way to avoid format strings and do it yourself in a very compact way. – SpacedMonkey Jun 25 '12 at 11:14
1

@SpacedMonkey - It is unfortunate that students are being judged on meaningless, unexplained criterion, with meaningless restrictions. Anyway, you reduced an 'operation' (IMO), by getting rid of a loop initializer. For this, +1. – ArjunShankar Jun 25 '12 at 11:18

ArjunShankar · Answer 3 · 2012-06-25T11:15:11.790

2

Your 'test tool' is probably broken, or expects you to do meaningless micro-optimizations while making code hard to read, which the compiler will do anyway.

You need to ask the user for the number of numbers => 1 scanf. You did this.
Next you need to ask the user for number numbers => scanf, number times. You did this.
Next you need to find the largest => loop number times, and compare. You already achieved this in the same loop as the previous one. And you did it well because you did the minimum possible number - 1 comparisons.
Next you need to print the result => 1 printf. You did this too.

This is the fastest you can possibly get^[1]. There is no scope for 'optimization'.

^{[1] If you had 2 cores, and were writing a multi-threaded program, you could do step 2 and 3 faster by pipelining them (see unkulunkulu's comments for why this is the fastest you can get).}

edited Jun 25 '12 at 11:15

answered Jun 25 '12 at 10:43

ArjunShankar

23,020
5
61
83

parallelizing couldn't help here, this comparison will be pipelined easily. Computing maximum while reading from file has zero overhead. – unkulunkulu Jun 25 '12 at 10:55
Thanks for response. With code i posted. Test tool says "161 operations". If set `max` to "-2147483647 - 1" then its "174 operations". I don't know if its broken. I REALLY need to pass this task, my life depends on it. – user1479645 Jun 25 '12 at 10:56
@unkulunkulu - Depends. I could split the loop into 2, input in the first, and then compare parallely in the second. With more than 2 CPUs, and enough input, this could be much faster than a pipeline. – ArjunShankar Jun 25 '12 at 10:57
How does the tool work? You upload the .c file, or you upload a binary? – ArjunShankar Jun 25 '12 at 10:59
@ArjunShankar, once again, reading while comparing is not slower than just reading. Not even a microsecond slower, that comparison doesn't add anything, and I bet you cannot scan all the numbers faster. Even 1-core processor is a parallel thing, it makes these comparisons in parallel. – unkulunkulu Jun 25 '12 at 11:02
@unkulunkulu - When you say, *Even 1-core processor is a parallel thing, it makes these comparisons in parallel* you're assuming a multiple issue processor, which is not always the case. BUT: As to *reading while comparing is not slower than just reading*, I agree. I realize that pipelining this is the fastest you can get. I will edit this in. – ArjunShankar Jun 25 '12 at 11:13
@ArjunShankar, yeah, I expressed that ambiguously, I meant that it makes comparisons in parallel with scanning, negating their own overhead. – unkulunkulu Jun 25 '12 at 11:17
anyway, the problem is the question is not about speed, but about some _operations_ (and we don't clearly know what they are). Also, answer by @kay, shows that your answer doesn't take comparisons of the loop variable into account. – unkulunkulu Jun 25 '12 at 11:20
@unkulunkulu - I was coming from [this point of view](http://stackoverflow.com/questions/8615489/how-fast-can-finding-the-max-in-an-array-possibly-get) when I initially included my footnote. Eventually, I realized that this is meaningless, because, like you said, we are limited by I/O, and because I realized there is no 'array' allowed. – ArjunShankar Jun 25 '12 at 11:20
@unkulunkulu - Right. Kay's answer is nice. My intention was to point out the the OP that the criterion of the test tool is broken, especially for a tool used in teaching a programming class. – ArjunShankar Jun 25 '12 at 11:24

score 2 · Answer 4 · answered Jun 25 '12 at 12:08

Should have used 1 scanf() instead of two:

#include <stdio.h>

int main() {
    int number;
    int max;
    int temp;

    scanf("%d %d", &number, &max);
    for ( int i = 1; i < number; i++ ) {
        scanf("%d", &temp);
        if ( temp > max ) {
            max = temp;
        }
    }
    printf("%d\n", max);
    return 0;
}

Sorry, and thanks to everyone! Hugs and kisses!

score 1 · Answer 5 · answered Jun 25 '12 at 11:20

1

You don't really need the i variable: you can use number itself.

Also you may want to abuse the for statement :)

#include <stdio.h>

int main(void) {
    int number;
    int max;
    int temp;

    for (scanf("%d", &number), scanf("%d", &max)
       ; --number && scanf("%d", &temp)
       ; )
    {
        if (temp > max) max = temp;
    }

    printf("%d\n", max);
    return 0;
}

answered Jun 25 '12 at 11:20

pmg

106,608
13
126
198

So we know you need to scanf("%d", &max); before the for() but @pmg still has a point. Get rid of i by using for ( ; --number; ) – SpacedMonkey Jun 25 '12 at 11:39

score -1 · Answer 6 · answered Jun 25 '12 at 14:11

-1

#include <stdio.h>

int main() {
    int number;
    int max;
    int temp,i;

    scanf("%d", &number);

    for ( i = 0; i < number; i++ ) {
        scanf("%d", &temp);
        if(i==0)
            max=temp;
        if ( temp > max ) {
            max = temp;
        }
    }

printf("max=%d\n", max);
return 0;

}

answered Jun 25 '12 at 14:11

Ling Tze Hock

41
1
7

Compliance with the conditions? – Ling Tze Hock Jun 25 '12 at 14:14
Does not meet the conditions? – Ling Tze Hock Jun 25 '12 at 15:41

How to find max int value from array

6 Answers6

Update 1:

Update 2: