10 weeks ago

John 910

Hyderabad

Question 1

Question 2

Question 3

26 days ago

Lokesh 310

Hyderabad

Question 1

Solution:

• Let the maximum absolute difference occur between Element $i$ and $i+1$, then, the maximum difference be Diff = A[i]-A[i+1]
• So insert a number between i and i+1, which is equal to A[i]+diff/2. The cost reduces by a value of (diff^2 - (diff/2)^2 - ((diff+1)/2)^2)
• Also note that adding a number at the front or last just increases the difference and does not decrease it.

Pseudocode:

long long getMinCost(vector<int> arr)
{
    long long cost = 0;
    long long diff = 0;
    for (long long i = 0; i < arr.size() - 1; i++)
    {
        diff = max(diff, abs(arr[i] - arr[i + 1]));
        cost += (arr[i] - arr[i + 1]) * (arr[i] - arr[i + 1]);
    }
    return (cost - diff * diff + (diff / 2) * (diff / 2) + ((diff + 1) / 2) * ((diff + 1) / 2));
}

Complexity:

• O(N)

26 days ago

Lokesh 310

Hyderabad

Question 2

Solution

• Precompute the prime or composite for every number until 10^4 (maximum value of A[i]) using prime sieve
• Find the number of prime and composite in the given array
• If no of prime = no of composite
  • Then output 0
  • Ordering is of the form PCPC......CP
• Else
  • x = (min(no of prime, no of composite)
  • ans = total sum - (sum of maximum x primes + sum of maximum x non-primes + (x+1)^th maximum of maximum element type(prime/composite)
  • let then maximum type(prime/composite) be denoted by M, minimum type by m
  • Order is of the form MmM.......MmM.

Pseudocode:

int minPenalty(vector<int> arr)
{
    vector<bool> is_prime(10001, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= 10000; i++)
        if (is_prime[i] && (long long)i * i <= 10000)
            for (int j = i * i; j <= 10000; j += i)
                is_prime[j] = false;
    int count = 0;
    vector<int> primes;
    vector<int> nonprime;
    for (int i = 0; i < arr.size(); i++)
    {
        if (is_prime[arr[i]])
        {
            count++;
            primes.push_back(arr[i]);
        }
        else
            nonprime.push_back(arr[i]);
    }

    sort(primes.begin(), primes.end());
    sort(nonprime.begin(), nonprime.end());
    int ans = 0;

    if (2 * count == arr.size())
        return 0;
    else
    {
        int x = min(count, (int)arr.size() - count);
        for (int i = 0; i < primes.size() - x; i++)
            ans += primes[i];
        for (int i = 0; i < nonprime.size() - x; i++)
            ans += nonprime[i];
        if (2 * count < arr.size())
            ans -= nonprime[nonprime.size() - x - 1];
        else
            ans -= primes[primes.size() - x - 1];
    }
    return ans;
}

Complexity:

• O(NloglogN),where N=10^4

26 days ago

Lokesh 310

Hyderabad

Question 3

Solution:

• To get the maximum number of positive prefix sums, the arrays should be sorted in descending order
• Sort the arr in descending order and count the number of positive prefix sums

PseudoCode:

long long  maxPosPrefixes(vector<long long > arr)
{
    sort(arr.rbegin(), arr.rend());
    long long prefixsum = 0;
    long long  ans = 0;
    for (long long  i = 0; i < arr.size(); i++)
    {
        prefixsum += arr[i];
        if (prefixsum > 0)
            ans++;
        else
            break;
    }
    return ans;
}

Complexity:

-O(NLOGN)