Write a function:
class Solution { public int solution(int[] A); }
that, given an array of N positive integers, returns the maximum number of trailing zeros of the number obtained by multiplying three different elements from the array. Numbers are considered different if they are at different positions in the array.
For example, given A = [7, 15, 6, 20, 5, 10], the function should return 3 (you can obtain three trailing zeros by taking the product of numbers 15, 20 and 10 or 20, 5 and 10).
For another example, given A = [25, 10, 25, 10, 32], the function should return 4 (you can obtain four trailing zeros by taking the product of numbers 25, 25 and 32).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..100,000];
- each element of array A is an integer within the range [1..1,000,000,000].
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A)
{
int max = 0;
for (var i = 0; i < A.Length - 2; i++) {
for (var j = i + 1; j < A.Length - 1; j++) {
for (var k = j + 1; k < A.Length; k++) {
BigInteger product = BigInteger.Multiply(BigInteger.Multiply(A[i], A[j]), A[k]);
var zeros = trailingZeros(product);
Console.WriteLine($"{product} - {zeros}");
if (zeros > max) {
max = zeros;
}
}
}
}
return max;
}
private int trailingZeros(BigInteger N) {
if (N == 0) {
return 0;
}
int count = 0;
while (N > 0 && N % 10 == 0) {
count++;
N /= 10;
}
return count;
}
}
using System;
using System.Numerics;
class Solution {
public int solution(int[] A)
{
int max = 0;
for (var i = 0; i < A.Length - 2; i++) {
for (var j = i + 1; j < A.Length - 1; j++) {
for (var k = j + 1; k < A.Length; k++) {
BigInteger product = BigInteger.Multiply(BigInteger.Multiply(A[i], A[j]), A[k]);
var zeros = trailingZeros(product);
Console.WriteLine($"{product} - {zeros}");
if (zeros > max) {
max = zeros;
}
}
}
}
return max;
}
private int trailingZeros(BigInteger N) {
if (N == 0) {
return 0;
}
int count = 0;
while (N > 0 && N % 10 == 0) {
count++;
N /= 10;
}
return count;
}
}
using System;
using System.Numerics;
class Solution {
public int solution(int[] A)
{
int max = 0;
for (var i = 0; i < A.Length - 2; i++) {
for (var j = i + 1; j < A.Length - 1; j++) {
for (var k = j + 1; k < A.Length; k++) {
BigInteger product = BigInteger.Multiply(BigInteger.Multiply(A[i], A[j]), A[k]);
var zeros = trailingZeros(product);
//Console.WriteLine($"{product} - {zeros}");
if (zeros > max) {
max = zeros;
}
}
}
}
return max;
}
private int trailingZeros(BigInteger N) {
if (N == 0) {
return 0;
}
int count = 0;
while (N > 0 && N % 10 == 0) {
count++;
N /= 10;
}
return count;
}
}
using System;
using System.Numerics;
class Solution {
public int solution(int[] A)
{
int max = 0;
for (var i = 0; i < A.Length - 2; i++) {
for (var j = i + 1; j < A.Length - 1; j++) {
for (var k = j + 1; k < A.Length; k++) {
BigInteger product = BigInteger.Multiply(BigInteger.Multiply(A[i], A[j]), A[k]);
var zeros = trailingZeros(product);
//Console.WriteLine($"{product} - {zeros}");
if (zeros > max) {
max = zeros;
}
}
}
}
return max;
}
private int trailingZeros(BigInteger N) {
if (N == 0) {
return 0;
}
int count = 0;
while (N > 0 && N % 10 == 0) {
count++;
N /= 10;
}
return count;
}
}
using System;
using System.Numerics;
class Solution {
public int solution(int[] A)
{
int max = 0;
for (var i = 0; i < A.Length - 2; i++) {
for (var j = i + 1; j < A.Length - 1; j++) {
for (var k = j + 1; k < A.Length; k++) {
BigInteger product = BigInteger.Multiply(BigInteger.Multiply(A[i], A[j]), A[k]);
var zeros = trailingZeros(product);
//Console.WriteLine($"{product} - {zeros}");
if (zeros > max) {
max = zeros;
}
}
}
}
return max;
}
private int trailingZeros(BigInteger N) {
if (N == 0) {
return 0;
}
int count = 0;
while (N > 0 && N % 10 == 0) {
count++;
N /= 10;
}
return count;
}
}
The following issues have been detected: timeout errors.
large test against greedy solutions, N <= 100000
running time: >6.00 sec., time limit: 0.45 sec.