Problems from interviews by maximum numbers: how to solve?

Nik_Set_72019-07-07 13:00:18

Algorithms

Nik_Set_7, 2019-07-07 13:00:18

There is such a task:
you need to write a function that takes an array of numbers as input (unsorted, let's say integers), also returns an array that contains:
- the maximum number A1
- three other maximum numbers A2, A3, A4, which, when multiplied, give A1
Started writing function with max selection and sorting, then I started writing nested loops, but I realized that there would be too many conditions and checks.
There is an idea that regular expressions can help here, but I don’t know yet how to implement it.

Answer the question

In order to leave comments, you need to log in

7 answer(s)

Sergey Sokolov, 2019-07-07
@Nik_Set_7

Sort in descending order and two cycles - not kosher?

in JS

const maxprod = arr => {
  const a = arr.slice().sort((a, b) => b - a);
  const max = a[0];
  const len = a.length;
  let iter = 0;
    
  for (let i = 1; i < len - 2; i++) {
    iter++;
    const A2 = a[i];
    const x2 = max / A2;
    if (!Number.isInteger(x2)) continue;
      
    for (let j = i + 1; j < len - 1; j++) {
      iter++;
      const A3 = a[j];
      const x3 = x2 / A3;
      if (!Number.isInteger(x3)) continue;
      
      if (!!~a.indexOf(x3)) {
        return [max, A2, A3, x3, iter]);
      }
    }
  }
  
  return false;
}

По сути циклов три, т.к. indexOf() всё равно перебирает массив.
Of the optimizations, only cutting off small tails, when the product becomes smaller than the desired one.
And checking each candidate for divisibility.
Another number of iterations is pushed into the tail of the result.

Tests

[
  [20,5,3,2,2], // [ 20, 5, 2, 2, 3 ]
  [7,9,4,60,5,3,2,2], // [ 60, 5, 4, 3, 4 ]
  [1,2,3,199], // false
  [2430,2431,2431,2431,1,1,1,2,3,5,7,9,11,13,15,17,19,23], // [ 2431, 17, 13, 11, 8 ]
].forEach(test => console.log(test, maxprod(test)));

�

⚡ Kotobotov ⚡, 2019-07-07
@angrySCV

regular expressions will not help you in this task
, read about this type of tasks here

#, 2019-07-08
@mindtester

adamos ,

2. Factorize A1 (this is much faster than iterating over the entire array into combinations of three elements).

it all depends on the size of the numbers. for large numbers this can be a daunting task
Nik_Set_7 , until I noticed a clarification - is the presence of divisors guaranteed in the general list?
in general, the maximum is found in one complete pass . it is necessary , but also sufficient .
and dances with divisors depend on nuances - the size of the list? does it fit RAM? or is it available only sequentially, from a slow source?.. if the divisors are guaranteed to be present, they can be found in .. I think the number of passes will definitely be less than for any sorting algorithm )) upd if the list is significantly longer than 3 elements ))
and is there a guarantee that divisors are present in the list? if not +values are not large +list is large +source is consistent and slow, maybe Adamos is right. well, for values no more than 8 bit integer, it will most likely be right unambiguously))

Dimonchik, 2019-07-07
@dimonchik2013

let's say integers

a good outfit
there, is there a case that integer multipliers "let's say" did not fall off?

John_Nash, 2019-07-08
@John_Nash

whole numbers, positive

Then, if we assume that the amount should be maximum. That's all simple.
Sort. Take 1st maximum. A1
Take the 2nd maximum (cycle from maximum to minimum) A2
Divide by the second maximum (current). Get cycle level 2. It also takes values less than or equal to. division result
Divide the quotient by A3, check if the result is in the list of values.
Once found, you can complete

vvs46, 2019-07-08
@vvs46

If I understand the problem correctly, my solution is:

Source

#include <iostream>
#include <windows.h>
#include <vector>
std::vector<int> DoTheJob(std::vector<int> v)
{

    int tmp;
    std::vector<int> result;
    bool flagfound = false;


    //sorting
    for(int i=0;i<v.size()-1;i++)
    {
        for (int j=i+1;j<v.size();j++)
        {
            if(v[j]>v[i])
            {
                tmp=v[i];
                v[i]=v[j];
                v[j]=tmp;
            };
        };
    };

    //sorting_end
    result.push_back(v[0]);
    for(int i=1; i<v.size()-2;i++)
    {
        if (flagfound)
                {
                    break;
                }
        for(int j=i+1;j<v.size()-1;j++)

        {
            if (flagfound)
                {
                    break;
                };
            for(int k=j+1;k<v.size();k++)
            {
                if (flagfound)
                {
                    break;
                };
                if(v[0]==v[i]*v[j]*v[k])
                    {
                        result.push_back(v[i]);
                        result.push_back(v[j]);
                        result.push_back(v[k]);
                        flagfound = true;
                    }
            };
        };
    }
    return result;
};
int main()
{   int q = 10;
    std::vector<int> v;
    for (int i=0;i<q;i++)
    {
        v.push_back((GetTickCount()+rand())%10);
        std::cout<< v[i]<<" ";
    };
    std::cout<<std::endl;
    std::vector<int> solution = DoTheJob(v);
    std::cout << "Max element: "<<solution[0];
    if (solution.size()==4)
    {
        std::cout<<", multipliers: "<<solution[1]<<", "<< solution[2]<<", "<<solution[3];
    }
    else
    std::cout<< ", no multipliers.";
    return 0;
}