array problem of finding number of edits needed

Question

Given an array arr containing positive elements and an integer K. In one operation you can pick an element of the array (suppose arr[i]) & break to p1,p2 insert p1 & p2. You need to find the minimum possible value.

This is my approach:

#include <bits/stdc++.h> 
using namespace std;
int main(){
int n,k; cin >> n >> k;
vector<int>v;
for(int i=0;i<n;i++)
{
    int x; cin >> x;
    v.push_back(x);
}
while(k--)
{
    int x,y;
    sort(v.begin(),v.end());
    int p=v[v.size()-1];
    vector<int>::iterator it;
    it=v.begin()+v.size()-1; 
    v.erase(it);
    if(p%2==0)
    {
        x=p/2,y=p/2;
    }
    else
    {
        x=p/2;
        y=p-x;
    }
    v.push_back(x);
    v.push_back(y);
}
cout << *max_element(v.begin(),v.end());
return 0;
}

Is it correct? If it is correct then (TC is n*k) is there any optimized solution possible?

Answer 1

As already stated in a comment, your algorithm cannot always provide the correct answer. This is a proposal of another algorithm.

Checking that a given max (= target) can be obtained in K operations is rather easy: for each element x=A[i], calculate the number of operations C(x) which are necessary for this particular element to become less than the target. The total number of needed operations is equal to the sum of the individual counts. We just have to compare the total obtained with K.

For example, C(x) = sup(x/target) -1, when sup(.) is equal to the lowest integer higher or equal than its input value. Just pay attention that C(0) = 0.

This checking of the validity of the target value can be optimised by sorting the array in decreasing order. This allows to stop the count when the array element becomes less than the target.

The minimum maximum value minmax is such that minmax can be validated by the above procedure, but not minmax-1. This can be performed by a binary search.

Global complexity: O(n log(Amax)), where Amax is the maximum element value.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int Count_elt (int x, int target) {
    if (x == 0) return 0;
    int count = x/target;
    if (target*count == x) count --;
    return count;
}

bool check_target (std::vector<int>& A, int K, int target) {
    int n = A.size();
    int count = 0;
    for (int val: A) {
        if ((val <= target) || count > K) break;
        count += Count_elt (val, target);
    }
    return count <= K;
}

int minmax (std::vector<int>& A, int K) {
    std::sort (A.begin(), A.end(), std::greater<int>());
    if (A[0] == 0) return 0;
    int limit_0 = 0;    // highest value such that check = false
    int limit_1 = A[0]; // lowest value such that check = true
    while (true) {
        if (limit_1 == limit_0 + 1) return limit_1;
        int target = (limit_0 + limit_1) / 2;
        bool test = check_target(A, K, target);
        if (test) {
            limit_1 = target;
        } else {
            limit_0 = target;
        }
    }
    return -1;
}

int main () {
    std::vector<int> A = {12, 3, 3, 9};
    int K = 3;
    int Count = minmax (A, K);
    std::cout << "Count = " << Count << "\n";
}