Skip to content

Instantly share code, notes, and snippets.

@IvanPizhenko

IvanPizhenko/highestProductOf3.c

Created September 22, 2016 23:02
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save IvanPizhenko/f1525b4442c43420e1c3abacf2e21e6d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save IvanPizhenko/f1525b4442c43420e1c3abacf2e21e6d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Ivan Pizhenko created this gist Sep 22, 2016.
    69 changes: 69 additions & 0 deletions highestProductOf3.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,69 @@
    /* Code example translated from Java to C */

    #include <stddef.h>

    int minInt(int a, int b)
    {
    return a < b ? a : b;
    }

    int maxInt(int a, int b)
    {
    return a > b ? a : b;
    }

    int highestProductOf3(const int* arrayOfInts, size_t size)
    {
    size_t i;

    if (size < 3)
    return 0; /* indicate error */

    /* We're going to start at the 3rd item (at index 2)
    so pre-populate highests and lowests based on the first 2 items.
    we could also start these as null and check below if they're set
    but this is arguably cleaner */
    int highest = maxInt(arrayOfInts[0], arrayOfInts[1]);
    int lowest = minInt(arrayOfInts[0], arrayOfInts[1]);

    int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
    int lowestProductOf2 = arrayOfInts[0] * arrayOfInts[1];

    /* except this one--we pre-populate it for the first /3/ items.
    this means in our first pass it'll check against itself, which is fine. */
    int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];

    /* walk through items, starting at index 2 */
    for (i = 2; i < size; i++) {
    int current = arrayOfInts[i];

    /* do we have a new highest product of 3?
    it's either the current highest,
    or the current times the highest product of two
    or the current times the lowest product of two */
    highestProductOf3 = maxInt(maxInt(
    highestProductOf3,
    current * highestProductOf2),
    current * lowestProductOf2);

    /* do we have a new highest product of two? */
    highestProductOf2 = maxInt(maxInt(
    highestProductOf2,
    current * highest),
    current * lowest);

    /* do we have a new lowest product of two? */
    lowestProductOf2 = minInt(minInt(
    lowestProductOf2,
    current * highest),
    current * lowest);

    /* do we have a new highest? */
    highest = maxInt(highest, current);

    /* do we have a new lowest? */
    lowest = minInt(lowest, current);
    }

    return highestProductOf3;
    }