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;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
int MaximumFives = 45; // maximum 5s
int Multipliers = 3; // number of multipliers
var resultsMatrix = new int[Multipliers+1,MaximumFives+5];
int maxTrailingZeros = 0;
for (int i = 0; i<Multipliers+1; i++)
for(int j = 0; j<MaximumFives+5; j++)
{
resultsMatrix[i, j] = -1;
}
resultsMatrix[0,0] = 0;
for (int p=0; p< A.Length; p++)
{
var current = DisectNumber(A[p]);
for (int i = Multipliers - 1; i >= 0; i--)
for (int j = 0; j < MaximumFives; j++)
{
if (resultsMatrix[i,j] != -1)
resultsMatrix[i + 1,j + current.Fives] =
Math.Max(resultsMatrix[i + 1, j + current.Fives], (resultsMatrix[i,j] + current.Twos));
maxTrailingZeros = Math.Max(maxTrailingZeros, Math.Min(j, resultsMatrix[Multipliers, j]));
}
}
}
}
Compilation failed: 1 error(s), 0 warnings Solution.cs(47,16): error CS0161: `Solution.solution(int[])': not all code paths return a value
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
int MaximumFives = 45; // maximum 5s
int Multipliers = 3; // number of multipliers
var resultsMatrix = new int[Multipliers+1,MaximumFives+5];
int maxTrailingZeros = 0;
for (int i = 0; i<Multipliers+1; i++)
for(int j = 0; j<MaximumFives+5; j++)
{
resultsMatrix[i, j] = -1;
}
resultsMatrix[0,0] = 0;
for (int p=0; p< A.Length; p++)
{
var current = DisectNumber(A[p]);
for (int i = Multipliers - 1; i >= 0; i--)
for (int j = 0; j < MaximumFives; j++)
{
if (resultsMatrix[i,j] != -1)
resultsMatrix[i + 1,j + current.Fives] =
Math.Max(resultsMatrix[i + 1, j + current.Fives], (resultsMatrix[i,j] + current.Twos));
maxTrailingZeros = Math.Max(maxTrailingZeros, Math.Min(j, resultsMatrix[Multipliers, j]));
}
}
}
}
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
int MaximumFives = 45; // maximum 5s
int Multipliers = 3; // number of multipliers
var resultsMatrix = new int[Multipliers+1,MaximumFives+5];
int maxTrailingZeros = 0;
for (int i = 0; i<Multipliers+1; i++)
for(int j = 0; j<MaximumFives+5; j++)
{
resultsMatrix[i, j] = -1;
}
resultsMatrix[0,0] = 0;
for (int p=0; p< A.Length; p++)
{
var current = DisectNumber(A[p]);
for (int i = Multipliers - 1; i >= 0; i--)
for (int j = 0; j < MaximumFives; j++)
{
if (resultsMatrix[i,j] != -1)
resultsMatrix[i + 1,j + current.Fives] =
Math.Max(resultsMatrix[i + 1, j + current.Fives], (resultsMatrix[i,j] + current.Twos));
maxTrailingZeros = Math.Max(maxTrailingZeros, Math.Min(j, resultsMatrix[Multipliers, j]));
}
}
return maxTrailingZeros;
}
}
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
int MaximumFives = 45; // maximum 5s
int Multipliers = 3; // number of multipliers
var resultsMatrix = new int[Multipliers+1,MaximumFives+5];
int maxTrailingZeros = 0;
for (int i = 0; i<Multipliers+1; i++)
for(int j = 0; j<MaximumFives+5; j++)
{
resultsMatrix[i, j] = -1;
}
resultsMatrix[0,0] = 0;
for (int p=0; p< A.Length; p++)
{
var current = DisectNumber(A[p]);
for (int i = Multipliers - 1; i >= 0; i--)
for (int j = 0; j < MaximumFives; j++)
{
if (resultsMatrix[i,j] != -1)
resultsMatrix[i + 1,j + current.Fives] =
Math.Max(resultsMatrix[i + 1, j + current.Fives], (resultsMatrix[i,j] + current.Twos));
maxTrailingZeros = Math.Max(maxTrailingZeros, Math.Min(j, resultsMatrix[Multipliers, j]));
}
}
return maxTrailingZeros;
}
}
using System;
public class NumberDisectData
{
public NumberDisectData(int twos, int fives)
{
Twos = twos;
Fives = fives;
}
public int Twos { get; set; }
public int Fives { get; set; }
public int Zeros
{
get
{
return Twos < Fives ? Twos : Fives;
}
}
public static NumberDisectData operator +(NumberDisectData n1, NumberDisectData n2)
{
return new NumberDisectData(n1.Twos + n2.Twos, n1.Fives + n2.Fives);
}
}
class Solution {
public static NumberDisectData DisectNumber(int number)
{
var fives = 0;
var twos = 0;
// calculate fives
while (number % 5 == 0)
{
fives++;
number = number / 5;
}
// calculate twos
while (number % 2 == 0)
{
twos++;
number = number / 2;
}
return new NumberDisectData(twos, fives);
}
public int solution(int[] A) {
int MaximumFives = 45; // maximum 5s
int Multipliers = 3; // number of multipliers
var resultsMatrix = new int[Multipliers+1,MaximumFives+5];
int maxTrailingZeros = 0;
for (int i = 0; i<Multipliers+1; i++)
for(int j = 0; j<MaximumFives+5; j++)
{
resultsMatrix[i, j] = -1;
}
resultsMatrix[0,0] = 0;
for (int p=0; p< A.Length; p++)
{
var current = DisectNumber(A[p]);
for (int i = Multipliers - 1; i >= 0; i--)
for (int j = 0; j < MaximumFives; j++)
{
if (resultsMatrix[i,j] != -1)
resultsMatrix[i + 1,j + current.Fives] =
Math.Max(resultsMatrix[i + 1, j + current.Fives], (resultsMatrix[i,j] + current.Twos));
maxTrailingZeros = Math.Max(maxTrailingZeros, Math.Min(j, resultsMatrix[Multipliers, j]));
}
}
return maxTrailingZeros;
}
}
The solution obtained perfect score.