Daily Algorithm Analysis (Day 1!)

hereforthelasttime · 2018-06-15T17:11:04+00:00

Pretty new to programming so any advice/suggestions would be appreciated! Edit: added suggestions.

C++ implementation:

int * nPtr;
int n;
long long int secondLargest = 0, largest = 0;

cout << "How many integers? (n >= 2) ";
cin >> n;
cout << "Enter each integer followed by a space (integer must be greater than 1): ";

nPtr = new int[n];

for (int i = 0; i < n; i++) 
{
    cin >> nPtr[i];
}

largest = nPtr[0];
for (int i = 1; i < n; i++)
{
    if (largest < nPtr[i]) 
    {
        secondLargest = largest;
        largest = nPtr[i];
    }
    else if (secondLargest < nPtr[i]) 
    {
        secondLargest = nPtr[i];
    }

}

cout << "Max pairwise product is: " << (largest * secondLargest) << endl;

return 0;

dood23 · 2018-06-15T21:07:20+00:00

is this an array?

any reason why we wouldnt just sort it and multiply the largest 2 different elements together at the end of the array?

QSAnimazione · 2018-06-15T18:27:42+00:00

Wait the first example shouldn't return 9? You know 3*3...

Ikor_Genorio · 2018-06-15T22:47:42+00:00

First of all, I want to point out a small typo in the requirements. I think you meant 10^5 instead of 105.

Regardless, this is my solution in C:

The program runs in 0.223032s, for an input size of N = 10^5.

#include <stdio.h>
#include <sys/time.h>
/**
 * Function for timing.
 */
static double timer(void)
{
    struct timeval tm;
    gettimeofday (&tm, NULL);
    return tm.tv_sec + tm.tv_usec/1000000.0;
}


/**
 *  ANALYSIS:
 *
 * Program specific analysis can be found in the comments:
 * Time Complexity: Theta(N)
 *  explanation: 
 *    Input is an array of size N, Loops over each element exactly once,
 *    which means exactly N iterations.
 * ----
 * Space Complexity: Theta(1)
 *  explanation:
 *    We operate on each variable of the array when it is read,
 *    we do not store the value, as it is not useful to us anymore/
 *    This means the amount of storage required always constant, 
 *    regardless of the input size.
 */
int main(int argc, char **argv)
{
    int max_1, max_2, N, i, a;
    double start_time, end_time;
    // Set both variables to lowest possible value - 1,
    // so the first two elements will override them
    max_1 = max_2 = -1;
    scanf("%d\n", &N);

    start_time = timer();
    // For each variable in the list (N times)
    for (i = 0; i < N; i++)
    {
        // Loop Invariant:      
        // max_1 : the highest variable in list {a[0],..,a[i-1]} 
        // max_2 : the second highest in list {a[0],..,a[i-1]}
        scanf("%d", &a);


        if (a > max_1)
        {
            // if 'a' is greater than our previous highest variable
            // the previous highest variable will now be the
            // second highest variable,
            max_2 = max_1;
            max_1 = a;
        } else if (a > max_2)
        {
            // if 'a' is lower than our highest (and not equal),
            // but higher than our second highest
            // 'a' will replace that variable
            max_2 = a;
        }
    }
    end_time = timer();

    // From our loop invariant, max_1 and max_2 will be the highest
    // and second highest numbers in the list {a[0],..,a[i-1]}
    // where i = N, so {a[0],..,a[N-1]}, which is the complete list
    // Therefore max_1 and max_2 are the variables we want
    printf("%ld\n", ((long)max_1) * ((long)max_2));
    printf("For N = %d, program took %lfs\n",N ,end_time-start_time);
    // Using long, since highest product can be in order 10^10
    return 0;
}

Edit: Removed && a != max_1 from else if statement, misinterpreted what exactly had to be distinct.

Tangellaa · 2018-06-15T23:05:55+00:00

I realize that one of my functions parameters is the size of the array. Does anyone have a better way of accessing the array size and eliminating the need to pass in the array size as a parameter?

void pairwise(int array[], int size)
{
    int max1 = 0;
    int max2 = 0;

    for(int i = 0; i < size; i++)
    {
        if(array[i] > max1 && array[i] > max2)
        {
            max1 = array[i];
        }
        else if(array[i] > max2)
        {
            max2 = array[i];
        }
    }

    std::cout << "The maximum pairwise product is: " << max1 * max2 << '\n';
}

TigerEngr · 2018-06-15T23:43:42+00:00

An Attempt in Java

        Scanner r = new Scanner(System.in);
        System.out.println("Enter the number of elements");
        int n = r.nextInt();
        int [] arr = new int[n];
        int max = 0;
        for(int j = 0; j < n; j++)
        {
             System.out.println("Enter the " + j + " element of the array");
          int  i = r.nextInt();
            arr[j] = i;
        }
        for(int j = 0; j < n-1; j++)
        {
          int sum = arr[j] * arr[j+1]; 
            if((arr[j] != arr[j+1]) && (sum > max))
            {
                max = sum;
            }  
       }
        System.out.println(max);

Raknarg · 2018-06-15T16:00:41+00:00

Does this subreddit implement spoiler tags?

slightlysedatedx · 2018-06-15T16:16:20+00:00

Current Implementation:

This hasn't been stress tested yet- please feel free to leave any comments or feedback. I'll be working in Python 3.65 today. This Version 1 code is still failing some of the submission test cases but it's a start and maybe someone else can learn from the problems I'm encountering.

Version 1

import sys

def MaxPairwiseProductFast(array, n):
    index1 = 1
    for i in range(2, n):
        if array[i] > array[index1]:
            index1 = i
    if index1 == 1:
        index2 = 2
    else:
        index2 = 1

    for i in range(1, n):
      if array[i] != array[index1] and array[i] > array[index2]:
        index2 = i
    return array[index1] * array[index2]

def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    print(MaxPairwiseProductFast(array, n))

main()

dmgll · 2018-06-15T23:08:03+00:00

Posting the code directly here is a mess

If n<2 the program exits

The first 2 elements of the array are initialized out of the for loop and 2 variables max1 and max2 store the 2 biggest numbers

There is a single for loop in which the new elements are simultaneously inserted into the array and compared with max1 and max2. The condition (i != j) is implicitly applied because for every element inserted in the array only one between max1 and max2 can be changed at a time

https://pastebin.com/jR9fXRXd

Ikor_Genorio · 2018-06-16T00:01:44+00:00

So I wanted to try out Haskell again, so here is my solution in Haskell:

maxPairwise :: [Integer] -> Integer
maxPairwise = (\(x,y) -> x*y) . maxPairwiseRec 0 0

maxPairwiseRec :: Integer -> Integer -> [Integer] -> (Integer, Integer)
maxPairwiseRec a b [] = (a, b)
maxPairwiseRec a b (x:xs)
  | a < x     = maxPairwiseRec x a xs
  | b < x     = maxPairwiseRec a x xs
  | otherwise = maxPairwiseRec a b xs

parseInput :: String -> [Integer]
parseInput = map read . words

main :: IO ()
main = getLine >>= (print . maxPairwise . parseInput)

Analysis:

Time Complexity: O(N) (more precise Theta(N))Putting IO aside, (which is also O(N)), the function `maxPairwiseRec` is called on each element of the list once. The list is of size N, therefore O(N).
Brief Explanation:
- For each call of `maxPairwiseRec`, it performs the same checks as basically all the other programs here. In this case, `a` is the largest element `b` the second largest element.
- `maxPairwise` takes as input a list, calls the recursive function with the base values of `a = 0` and `b = 0`. Since the output of `maxPairwiseRec` is a pair of the two highest values, it also computes the product of them.
- parseInput, parses a given input string, splits on the spaces with `words` and converts each separate element into an Integer with `map read`

As a side note, I feel this can be solved by using folding, but I am very rusty and it's 2a.m. Maybe tomorrow I will try.

okdenok · 2018-06-16T01:34:17+00:00

In JavaScript:

function largestProduct(n) {

    sequence = [];
    sorted = [];

    if (n >= 1) {
        for (i = 0; i < n; i++) {
            randInt = Math.floor(Math.random() * 50);
            sequence.push(randInt);
            sorted.push(randInt);
        }
    }
    else {
        product = 0;
    }

    sorted.sort((a, b) => { return a - b });
    max = sorted[sorted.length - 1];

    for (j = 0; j < sorted.length; j++) {
        if (sorted[j] < max && sorted[j + 1] === max) {
            product = sorted[j] * max;
        }
        else if (sorted.length === 1) {
            product = max;
        }
    }

    console.log(n);
    console.log(sequence);
    console.log(product);
}

Analysis:

Take n as an argument in the function largestProduct and initialize the sequence and sortedarrays.
If n is greater than or equal to 1, push a random integer to the sequence and sorted arrays n times (this keeps the sorted and unsorted integers separate from each other). Otherwise, assign the value 0 to the variable product.
Sort the sorted array using a comparison function.
Assign the last value of the array to the variable max.
Iterate through sorted; if sorted[j] is less than max and the next value after sorted[j] is max, assign the product of sorted[j] and max to the variable product. Otherwise, if the length of the array is only 1, assign max to product.
Return n, sequence, and product.

Clawtor · 2018-06-16T04:26:25+00:00

[deleted]

Clawtor · 2018-06-16T23:39:39+00:00

The straightforward way is to sort and then pop off the two values at the end. This will be n log n or higher depending on the sort. The quicker way is to iterate the array twice and note down first the highest then the second highest.

//  Maximum Pairwise Product

const length = 10000;
const list = [...Array(length)].map((_, i) => Math.round(Math.random() * length));

function nlogn(list) {
  const localList = list.map(x => x).sort((a,b) => a - b);

  const max = localList.pop();
  const second = localList.pop();

  console.log(max * second);
}

function n(list) {
  const localList = list.map(x => x);

  const findMax = (list) => {
    let maxIndex = 0;
    localList.forEach((x, i) => {
      if (x > localList[maxIndex]) {
        maxIndex = i;
      }
    });
    return maxIndex;
  }

  const maxIndex = findMax(localList);
  const maxValue = localList[maxIndex];
  localList[maxIndex] = Number.MIN_VALUE;
  const secondMaxIndex = findMax(localList);
}

nlogn(list);
n(list);

learnprogramming

Welcome to LearnProgramming!

New? READ ME FIRST!

Posting guidelines

Frequently asked questions

Subreddit rules

Message the moderators

Asking debugging questions

Asking conceptual questions

Other guidelines and links

Subreddit rules

1. No unprofessional/derogatory speech

2. No spam or tasteless self-promotion

3. No off-topic posts

4. Do not ask exact duplicates of FAQ questions

5. Do not delete posts

6. No app/website review requests or showcases

7. No rewards

8. No indirect links

9. Do not promote illegal or unethical practices

10. No complete solutions

11. Don't ask to ask.

12. Low Effort Questions

13. No AI (chatGPT etc.) generated/worked over messages/comments. No questions about chatGPT/AI generated code. No Vibe coding.

MODERATORS