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 <limits.h>) 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
– unwind, Commented Jun 25, 2012 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
– ArjunShankar, Commented Jun 25, 2012 at 10:26
I don't think that that problem could be solved with less operations ...? — Kijewski
– Kijewski, Commented Jun 25, 2012 at 10:30

Community · Accepted Answer · 2017-05-23 12:12:27Z

4

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;
}

edited May 23, 2017 at 12:12

CommunityBot

11 silver badge

answered Jun 25, 2012 at 11:04

Kijewski

26.1k14 gold badges108 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

unkulunkulu Over a year ago

positive was about the number of elements only

Kijewski Over a year ago

@unkulunkulu, I read it wrong, sorry. I leave the task for OP to change it back to signed. ;-)

user1479645 Over a year ago

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?

Kijewski Over a year ago

@user1479645 now using manual loop unrolling.

SpacedMonkey · Accepted Answer · 2012-06-25 10:42:27Z

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, 2012 at 10:42

SpacedMonkey

2,7731 gold badge17 silver badges17 bronze badges

7 Comments

SpacedMonkey Over a year ago

Sure, use INT_MIN instead of 0

SpacedMonkey Over a year ago

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.

user1479645 Over a year ago

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

ArjunShankar Over a year ago

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 Over a year ago

@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 · Accepted Answer · 2012-06-25 11:15:11Z

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, 2012 at 11:15

answered Jun 25, 2012 at 10:43

ArjunShankar

23.9k6 gold badges64 silver badges85 bronze badges

10 Comments

unkulunkulu Over a year ago

parallelizing couldn't help here, this comparison will be pipelined easily. Computing maximum while reading from file has zero overhead.

user1479645 Over a year ago

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.

ArjunShankar Over a year ago

@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 Over a year ago

How does the tool work? You upload the .c file, or you upload a binary?

unkulunkulu Over a year ago

@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.

|

user1479645 · Accepted Answer · 2012-06-25 12:08:38Z

2

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!

answered Jun 25, 2012 at 12:08

user1479645

515 bronze badges

Comments

pmg · Accepted Answer · 2012-06-25 11:20:39Z

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, 2012 at 11:20

pmg

109k14 gold badges132 silver badges203 bronze badges

1 Comment

SpacedMonkey Over a year ago

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; )

Ling Tze Hock · Accepted Answer · 2012-06-25 14:11:28Z

-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, 2012 at 14:11

Ling Tze Hock

411 silver badge7 bronze badges

2 Comments

Ling Tze Hock Over a year ago

Compliance with the conditions?

Ling Tze Hock Over a year ago

Does not meet the conditions?

Collectives™ on Stack Overflow

How to find max int value from array

6 Answers 6

Update 1:

Update 2:

4 Comments

7 Comments

10 Comments

Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Update 1:

Update 2:

4 Comments

7 Comments

10 Comments

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related