How can I improve my algorithm? Degree of divisibility question

user_13834503 0
Viewed 842

Hey guys I will explain the question below.

keys = list of integers I have to find max degree of divisibility of elements in keys. But When I calculate the degree of divisibility I should just consider the keys element. for example:

 keys = [2,4,8,2]
 2 = [2,2] degree of divisibility is 2
 4 = [2,4,2] degree of divisibility is 3
 8 = [2,4,8,2] degree of divisibility is 4 so we choose 8 with 4 degrees of divisibility.

after that we have to calculate

 if maxDegreeOfDivisibility(4 in our case) * 10^5 < validityPeriod* instructionCount then its 
 true.

and we return 1 and 4*10^5. I hope I explain the question if u guys have any questions about the question :D I can answer.

public static List<Integer> encryptionValidity(int instructionCount, int validityPeriod, 
List<Integer> keys) {
List<Integer> result = Arrays.asList(0, 0);
Map<Integer, Integer> degreeOfDivisibilityCache = new HashMap<>();

for (int i: keys) {
    Integer degreeOfDivisibility = degreeOfDivisibilityCache.getOrDefault(i, -1);

    if (degreeOfDivisibility == -1) {
        int count = 0;
        for (int j : keys) {
            if (j > 0 && i % j == 0) {
                count++;
            }
        }
        degreeOfDivisibilityCache.put(i, count);
    }
}

int maxDegreeOfDivisibility = degreeOfDivisibilityCache.values().stream()
        .max(Comparator.comparingInt(Integer::intValue)).orElse(0);
int s = maxDegreeOfDivisibility * 10000;
result.set(1, s);

BigInteger ic = BigInteger.valueOf(instructionCount);
BigInteger a = ic.multiply(BigInteger.valueOf(validityPeriod));
if (a.compareTo(BigInteger.valueOf(s)) > 0) {
    result.set(0, 1);
}
return result;
}
algorithm java
2 Answers
  1. Sort the numbers, largest first. Flag each one as being a candidate.
  2. For each number that is still a candidate:
    2.1. Count how many of the numbers after it divide into it. Mark each such number as no longer a candidate.
  3. Search the list for the largest count from step 2.1. That count is the Degree of Divisibility of the original list.

Example:

  1. [2,4,8,2,3,6] (before sorting)
  2. [8*,6*,4*,3*,2*,2*] -- '*' means "is a candidate"
  • check 8: [8*,6*,4,3*,2,2] -- divisible by 4 (8,4,2,2)
  • check 6: [8*,6*,4,3,2,2] -- divisible by 4 (6,3,2,2)
  • the rest don't need checking
  1. The answer is 4.
user_17668310
  1. Declare 32 buckets, each signifying an integer's most significant bit
  2. Scan through the keys, record their occurrence count and put unique instances in their respective buckets (unsorted), and flag as candidate
  3. Scan the buckets, in descending order of the most significant bit it represents. Compare only with contents of buckets of lower bits.
    • 3.1 On a divisible match, aggregate current count with occurrence count in step 2 & clear that number's candidacy flag
    • 3.2 If current count > current record holder, set record holder = this key & current count

Example: [19, 4, 12, 6, 4, 3, 8]

  • Occurrences: {19: 1, 4: 2, 12: 1, 6: 1, 3: 1, 8: 1}
  • Bucket #16: [19*]
  • Bucket #8: [12*, 8*]
  • Bucket #4: [4*, 6*]
  • Bucket #2: [3*]
  1. Scan 19 => 1(self); set record: (19, 1)
  2. Scan 12 => 1(self) + 2(from 4) + 1(from 6) + 1(from 3) = 5; clear 4, 6, 3; set record: (12, 5)
  3. Scan 8 => 2
  4. Skip 4, 6, 3

Time Complexity: if n is total integer count and m is number of unique integers, O(n) + O(m^2) in BigO notation, but actually O(n) + C*(m^2)/3 (for some constant C)

Analysis:

First scan in step 1: O(n)

Bucket scan: Worst case (full buckets) is inverted binary tree. This is an infinite series that sums to 1/3 (See related Wikipedia articles: here and here)

Credits to Rick James for candidate flag idea.

user_172000440
Related