In this HackerEarth Sequences problem solution you are given two integers X and Y. your task is to determine the sequence of real numbers with the minimum size such that the sum and product of the numbers in the sequence are X and Y respectively. Also, print the size of the sequence only. if no such sequences exist, then print -1.


HackerEarth Sequences problem solution


HackerEarth Sequences problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

bool check(int n,int y,int x){
    double v = temp(n,x);
    return (v >= y );
}

double temp(int n,int x){
    return pow(x*1.0/n, n);
}

int main() {
    int t;
    cin>>t;
    while(t--) {
    int x,y;
    cin>>x>>y;
    int high = (int)floor(x/exp(1.0));
    int low = 1;
    if (x == y) cout<<1<<endl;
    else if (!check(high,y,x)) cout<<-1<<endl;
    else {
        while(high - low > 1){
            int mid = (high+low)/2;
            if (check(mid,y,x)) high = mid;
            else low = mid;
        }
        cout<<high<<endl;
      }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6 + 17;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int x, y;
        cin >> x >> y;
        bool done = 0;
        if(x == y)
            cout << "1\n";
        else{
            for(int i = 2; !done && i < 100; i++)
                if(pow(x / double(i), i) >= y){
                    cout << i << '\n';
                    done = 1;
            }
            if(!done)
                cout << "-1\n";
        }
    }
}