You are given an array A consisting of N integers.
For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.
For example, consider integer N = 5 and array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6For the following elements:
- A[0] = 3, the non-divisors are: 2, 6,
- A[1] = 1, the non-divisors are: 3, 2, 3, 6,
- A[2] = 2, the non-divisors are: 3, 3, 6,
- A[3] = 3, the non-divisors are: 2, 6,
- A[4] = 6, there aren't any non-divisors.
Write a function:
class Solution { public int[] solution(int[] A); }
that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.
Result array should be returned as an array of integers.
For example, given:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6the function should return [2, 4, 3, 2, 0], as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in C# 5.0 with .NET 4.5 (Mono)
var countOccurrenceDictionary = new Dictionary<int, int>();
for (int i = 0; i < A.Length; i++)
{
if (countOccurrenceDictionary.ContainsKey(A[i]))
{
countOccurrenceDictionary[A[i]]++;
}
else
{
countOccurrenceDictionary.Add(A[i], 1);
}
}
int[] result = new int[A.Length];
for (int i = 0; i < A.Length; i++)
{
int count = 0;
for (int j = 1; j < Math.Sqrt(A[i]) + 1; j++)
{
if (countOccurrenceDictionary.ContainsKey(j) && A[i]%j == 0)
{
if (j != A[i])
{
count += countOccurrenceDictionary[j];
}
int divisor = A[i]/j;
if (divisor >= Math.Sqrt(A[i]) + 1)
{
if (countOccurrenceDictionary.ContainsKey(divisor) && A[i] % divisor == 0)
{
if (divisor != A[i])
{
count += countOccurrenceDictionary[divisor];
}
}
}
}
}
result[i] = A.Length - count - countOccurrenceDictionary[A[i]];
}
return result;
}
}
Solution.cs(11,45): error CS0246: The type or namespace name `Dictionary' could not be found. Are you missing `System.Collections.Generic' using directive? Compilation failed: 1 error(s), 0 warnings
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in C# 5.0 with .NET 4.5 (Mono)
var countOccurrenceDictionary = new Dictionary<int, int>();
for (int i = 0; i < A.Length; i++)
{
if (countOccurrenceDictionary.ContainsKey(A[i]))
{
countOccurrenceDictionary[A[i]]++;
}
else
{
countOccurrenceDictionary.Add(A[i], 1);
}
}
int[] result = new int[A.Length];
for (int i = 0; i < A.Length; i++)
{
int count = 0;
for (int j = 1; j < Math.Sqrt(A[i]) + 1; j++)
{
if (countOccurrenceDictionary.ContainsKey(j) && A[i]%j == 0)
{
if (j != A[i])
{
count += countOccurrenceDictionary[j];
}
int divisor = A[i]/j;
if (divisor >= Math.Sqrt(A[i]) + 1)
{
if (countOccurrenceDictionary.ContainsKey(divisor) && A[i] % divisor == 0)
{
if (divisor != A[i])
{
count += countOccurrenceDictionary[divisor];
}
}
}
}
}
result[i] = A.Length - count - countOccurrenceDictionary[A[i]];
}
return result;
}
}
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in C# 5.0 with .NET 4.5 (Mono)
var countOccurrenceDictionary = new Dictionary<int, int>();
for (int i = 0; i < A.Length; i++)
{
if (countOccurrenceDictionary.ContainsKey(A[i]))
{
countOccurrenceDictionary[A[i]]++;
}
else
{
countOccurrenceDictionary.Add(A[i], 1);
}
}
int[] result = new int[A.Length];
for (int i = 0; i < A.Length; i++)
{
int count = 0;
for (int j = 1; j < Math.Sqrt(A[i]) + 1; j++)
{
if (countOccurrenceDictionary.ContainsKey(j) && A[i]%j == 0)
{
if (j != A[i])
{
count += countOccurrenceDictionary[j];
}
int divisor = A[i]/j;
if (divisor >= Math.Sqrt(A[i]) + 1)
{
if (countOccurrenceDictionary.ContainsKey(divisor) && A[i] % divisor == 0)
{
if (divisor != A[i])
{
count += countOccurrenceDictionary[divisor];
}
}
}
}
}
result[i] = A.Length - count - countOccurrenceDictionary[A[i]];
}
return result;
}
}
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in C# 5.0 with .NET 4.5 (Mono)
var countOccurrenceDictionary = new Dictionary<int, int>();
for (int i = 0; i < A.Length; i++)
{
if (countOccurrenceDictionary.ContainsKey(A[i]))
{
countOccurrenceDictionary[A[i]]++;
}
else
{
countOccurrenceDictionary.Add(A[i], 1);
}
}
int[] result = new int[A.Length];
for (int i = 0; i < A.Length; i++)
{
int count = 0;
for (int j = 1; j < Math.Sqrt(A[i]) + 1; j++)
{
if (countOccurrenceDictionary.ContainsKey(j) && A[i]%j == 0)
{
if (j != A[i])
{
count += countOccurrenceDictionary[j];
}
int divisor = A[i]/j;
if (divisor >= Math.Sqrt(A[i]) + 1)
{
if (countOccurrenceDictionary.ContainsKey(divisor) && A[i] % divisor == 0)
{
if (divisor != A[i])
{
count += countOccurrenceDictionary[divisor];
}
}
}
}
}
result[i] = A.Length - count - countOccurrenceDictionary[A[i]];
}
return result;
}
}
The following issues have been detected: wrong answers, timeout errors.
small, random numbers, length = 100
got [99, 89, 97, 99, 99, 9.. expected [98, 89, 97, 99, 99, 9..
medium, random numbers length = 5,000
got [4994, 4993, 4995, 4995, 4990.. expected [4994, 4989, 4995, 4991, 4986..
large, random numbers, length = ~30,000
got .., 29989, 29999, 29998, 29999, 29996, 299.. expected .., 29989, 29999, 29997, 29999, 29994, 299..
large, all the same values, length = 50,000
running time: 0.57 sec., time limit: 0.53 sec.