Last Updated : 09 Nov, 2023
Improve
Given an array key of size n, instruction count representing the number of keys a hijacker can test per second, during a total validity period which is the average time to find a message key, determine if the encrypted information remains confidential throughout its validity period. Each function will return two items of information as integers:
- Can a hijacker crack the code within the period? (1 if true, 0 if false)
- The strength of the encryption, that is, the number of keys that must be tested to break the encryption.
The strength of the encryption is determined as follows:
- The degree of divisibility of an element is the number of elements in the array keys that are greater than 1 and are divisors of the element.
- The element m that has the maximum number of divisors (or degree of divisibility) in keys is used to determine the strength of the encryption which is defined as (the degree of divisibility of m)* 10^5.
- The list may contain duplicates. If keys [2, 4, 4] the divisibility of each 4 element is 3.
Examples:
Input: instructionCount = 1000, validityPeriod = 10000, n = 4, keys = [2, 4, 8, 2]
Output: 1 400000
Explanation: The element m that has the maximum number of divisors is 8 and its degree of divisibility is 4. The strength of encryption is 4* 10^5= 400000, the number of keys that must be tested to break the encryption. The hijacker’s total processing 1000 * 10000 = 10000000. The hijacker only can test 10000000 during the validity period. The information can be decrypted during the validity period so return 1 in the first position of the return array and 400000 in the second.Input: instructionCount = 100, validityPeriod = 1000, n=2, keys = [2, 4]
Output: 0 200000
Explanation: The element m that has the maximum number of divisors is 4 and its degree of divisibility is 2. The strength of encryption = 2*10^5= 200000, the number of keys that must be tested to break the encryption. The hijacker’s total processing 100*1000= 100000. The hijacker can only test 100000 keys during the validity period. The information cannot be decrypted during the validity period so return 0 in the first position of the return array and 200000 in the second.
Approach: To solve the problem follow the below steps:
- Create a frequency map mp to count the occurrences of each element in the keys vector .
- For each element in the keys vector.
- Iterate through possible divisors of element up to its square root and check whether it is present in vector key or not.
- Count the occurrences of element in the keys vector, considering duplicates.
- Update maxi if a larger count is found.
- Calculate the total number of keys an attacker can test (var = instructCount * validPeriod).
- Check if var is greater than or equal to maxi * 100000 (strength of encryption).
- If true, the hijacker can crack the code, return {1, maxi * 100000}.
- If false, the hijacker can’t crack the code, return {0, maxi * 100000}.
Below is the code for the above approach:
C++
// C++ program to check encription validity
#include <bits/stdc++.h>
using namespace std;
// Function to calculate encryption validity
vector<int> encrptionValidity(int instructCount,
int validPeriod,
vector<int> keys)
{
unordered_map<int, int> mp;
int maxi = 0;
// Count the frequency of each key
for (auto i : keys) {
mp[i]++;
}
// Iterate through each key
for (int i = 0; i < keys.size(); i++) {
int num = keys[i], count = 0;
// Iterate through each possible
// divisor of num
for (int j = 1; j <= sqrt(num); j++) {
// If j is a divisor of num and
// present in 'keys', count it
if (num % j == 0) {
if (mp.count(j)) {
count += mp[j];
}
// If j is not equal to num/j
// and present in 'keys' count
// num/j as well as divisors
// exist in pairs
if (j != num / j && mp.count(num / j)) {
count += mp[num / j];
}
}
}
maxi = max(count, maxi);
}
unsigned long long var = instructCount * validPeriod;
if (var >= maxi * 100000)
return { 1, maxi * 100000 };
return { 0, maxi * 100000 };
}
// Driver code
int main()
{
int instructCount, validPeriod, n;
instructCount = 1000, validPeriod = 10000, n = 4;
vector<int> keys = { 2, 4, 8, 2 };
vector<int> res1 = encrptionValidity(instructCount,
validPeriod, keys);
// Function Call
cout << res1[0] << " " << res1[1] << endl;
instructCount = 100, validPeriod = 1000, n = 2;
keys = { 2, 4 };
vector<int> res2 = encrptionValidity(instructCount,
validPeriod, keys);
// Function Call
cout << res2[0] << " " << res2[1] << endl;
return 0;
}
Java
// Java program to check encription validity
import java.util.*;
// Function to calculate encryption validity
public class EncryptionValidity
{
public static List<Integer> encryptionValidity(int instructCount, int validPeriod, List<Integer> keys)
{
Map<Integer, Integer> mp = new HashMap<>();
int maxi = 0;
// Count the frequency of each element
for (int i : keys)
{
mp.put(i, mp.getOrDefault(i, 0) + 1);
}
// Iterate through each key
for (int i = 0; i < keys.size(); i++)
{
int num = keys.get(i);
int count = 0;
// Iterate through each possible divisor of num
for (int j = 1; j <= Math.sqrt(num); j++)
{
// If j is a divisor of num and present in 'keys', count it
if (num % j == 0)
{
if (mp.containsKey(j))
{
count += mp.get(j);
}
// If j is not equal to num/j and present in 'keys',
// count num/j as well as divisors exist in pairs
if (j != num / j && mp.containsKey(num / j))
{
count += mp.get(num / j);
}
}
}
maxi = Math.max(count, maxi);
}
long var = (long) instructCount * validPeriod;
if (var >= maxi * 100000)
{
return Arrays.asList(1, (int) (maxi * 100000));
}
return Arrays.asList(0, (int) (maxi * 100000));
}
// Driver code
public static void main(String[] args) {
int instructCount, validPeriod, n;
instructCount = 1000;
validPeriod = 10000;
n = 4;
List<Integer> keys = Arrays.asList(2, 4, 8, 2);
List<Integer> res1 = encryptionValidity(instructCount, validPeriod, keys);
System.out.println(res1.get(0) + " " + res1.get(1));
instructCount = 100;
validPeriod = 1000;
n = 2;
keys = Arrays.asList(2, 4);
List<Integer> res2 = encryptionValidity(instructCount, validPeriod, keys);
System.out.println(res2.get(0) + " " + res2.get(1));
}
}
// This code is contributed by
// Abhishek Kumar
Python3
# Python program to check encription validity
import math
# Function to calculate encryption validity
def encryption_validity(instruct_count, valid_period, keys):
mp = {}
maxi = 0
# Count the frequency of each key
for i in keys:
mp[i] = mp.get(i, 0) + 1
# Iterate through each key
for i in range(len(keys)):
num = keys[i]
count = 0
# Iterate through each possible divisor of num
for j in range(1, int(math.sqrt(num)) + 1):
# If j is a divisor of num and present in 'keys', count it
if num % j == 0:
if j in mp:
count += mp[j]
# If j is not equal to num/j and present in 'keys',
# count num/j as well as divisors exist in pairs
if j != num // j and num // j in mp:
count += mp[num // j]
maxi = max(count, maxi)
var = instruct_count * valid_period
if var >= maxi * 100000:
return [1, maxi * 100000]
return [0, maxi * 100000]
# Driver code
if __name__ == "__main__":
instruct_count, valid_period, n = 1000, 10000, 4
keys = [2, 4, 8, 2]
res1 = encryption_validity(instruct_count, valid_period, keys)
print(res1[0], res1[1])
instruct_count, valid_period, n = 100, 1000, 2
keys = [2, 4]
res2 = encryption_validity(instruct_count, valid_period, keys)
print(res2[0], res2[1])
# This code is contributed by
# Abhishek Kumar
C#
// C# program to check encryption validity
using System;
using System.Collections.Generic;
using System.Linq;
public class EncryptionValidity {
public static List<int>
encryptionValidity(int instructCount, int validPeriod,
List<int> keys)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
int maxi = 0;
// Count the frequency of each element
foreach(int i in keys)
{
if (mp.ContainsKey(i)) {
mp[i]++;
}
else {
mp[i] = 1;
}
}
// Iterate through each key
for (int i = 0; i < keys.Count; i++) {
int num = keys[i];
int count = 0;
// Iterate through each possible divisor of num
for (int j = 1; j <= Math.Sqrt(num); j++) {
// If j is a divisor of num and present in
// 'keys', count it
if (num % j == 0) {
if (mp.ContainsKey(j)) {
count += mp[j];
}
// If j is not equal to num/j and
// present in 'keys', count num/j as
// well as divisors exist in pairs
if (j != num / j
&& mp.ContainsKey(num / j)) {
count += mp[num / j];
}
}
}
maxi = Math.Max(count, maxi);
}
long var = (long)instructCount * validPeriod;
if (var >= maxi * 100000) {
return new List<int>{ 1, (int)(maxi * 100000) };
}
return new List<int>{ 0, (int)(maxi * 100000) };
}
// Driver code
public static void Main(string[] args)
{
int instructCount, validPeriod;
instructCount = 1000;
validPeriod = 10000;
List<int> keys = new List<int>{ 2, 4, 8, 2 };
List<int> res1 = encryptionValidity(
instructCount, validPeriod, keys);
Console.WriteLine(res1[0] + " " + res1[1]);
instructCount = 100;
validPeriod = 1000;
keys = new List<int>{ 2, 4 };
List<int> res2 = encryptionValidity(
instructCount, validPeriod, keys);
Console.WriteLine(res2[0] + " " + res2[1]);
}
}
// This code is contributed by ragul21
Javascript
// JavaScript program to check encription validity
// Function to calculate encryption validity
function encryptionValidity(instructCount, validPeriod, keys) {
const mp = new Map();
let maxi = 0;
// Count the frequency of each key
for (const key of keys) {
if (mp.has(key)) {
mp.set(key, mp.get(key) + 1);
} else {
mp.set(key, 1);
}
}
// Iterate through each key
for (let i = 0; i < keys.length; i++) {
const num = keys[i];
let count = 0;
// Iterate through each possible
// divisor of num
for (let j = 1; j <= Math.sqrt(num); j++) {
// If j is a divisor of num and
// present in 'keys', count it
if (num % j === 0) {
if (mp.has(j)) {
count += mp.get(j);
}
// If j is not equal to num/j
// and present in 'keys' count
// num/j as well as divisors
// exist in pairs
if (j !== num / j && mp.has(num / j)) {
count += mp.get(num / j);
}
}
}
maxi = Math.max(count, maxi);
}
const varValue = instructCount * validPeriod;
if (varValue >= maxi * 100000) {
return [1, maxi * 100000];
}
return [0, maxi * 100000];
}
// Driver code
const instructCount1 = 1000;
const validPeriod1 = 10000;
const keys1 = [2, 4, 8, 2];
// Function Call
const res1 = encryptionValidity(instructCount1, validPeriod1, keys1);
console.log(res1[0], res1[1]);
const instructCount2 = 100;
const validPeriod2 = 1000;
const keys2 = [2, 4];
// Function Call
const res2 = encryptionValidity(instructCount2, validPeriod2, keys2);
console.log(res2[0], res2[1]);
Output
1 4000000 200000
Time Complexity: O(n*(sqrt(n))
Auxiliary Space: O(n)
abhishek9202
Improve
Previous Article
Information Security and Cyber Laws
Next Article
Minimum number of operations required to vanish all elements
