Task description
You are given a non-empty zero-indexed 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:
The sequence should be returned as:
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.
Assume that:
// you can also use imports, for example: // import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int[] solution(int[] A) { // write your code in Java SE 8 int[] result=new int[A.length]; int k=0,count=0; for(int i=0;i<A.length;i++){ count=0; for(int j=0;j<A.length;j++){ if(i!=j){ if(A[i]%A[j]!=0){ count++; } } } result[k]=count; k++; } return result; } }
Analysis
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:
Write a function:
- 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[6] = 6, there aren't any non-divisors.
that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.class Solution { public int[] solution(int[] A); }
The sequence should be returned as:
For example, given:
- a structure Results (in C), or
- a vector of integers (in C++), or
- a record Results (in Pascal), or
- an array of integers (in any other programming language).
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.
Assume that:
Complexity:
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
Elements of input arrays can be modified.
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
// you can also use imports, for example: // import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int[] solution(int[] A) { // write your code in Java SE 8 int[] result=new int[A.length]; int k=0,count=0; for(int i=0;i<A.length;i++){ count=0; for(int j=0;j<A.length;j++){ if(i!=j){ if(A[i]%A[j]!=0){ count++; } } } result[k]=count; k++; } return result; } }
Analysis summary
The following issues have been detected: timeout errors.
Detected time complexity:
O(N ** 2)
O(N ** 2)
expand allExample tests
expand allCorrectness tests
expand allPerformance tests
large_range
1, 2, ..., N, length = ~20,000
1, 2, ..., N, length = ~20,000
TIMEOUT ERROR
running time: >9.00 sec., time limit: 3.53 sec.
running time: >9.00 sec., time limit: 3.53 sec.
large_random
large, random numbers, length = ~30,000
large, random numbers, length = ~30,000
TIMEOUT ERROR
running time: >10.00 sec., time limit: 4.04 sec.
running time: >10.00 sec., time limit: 4.04 sec.
large_extreme
large, all the same values, length = 50,000
large, all the same values, length = 50,000
TIMEOUT ERROR
running time: >11.00 sec., time limit: 5.05 sec.
running time: >11.00 sec., time limit: 5.05 sec.
Comments
Post a Comment