eli delpierli eli delpierli - 15 days ago 6
C++ Question

acending repetitious function without array 1 22 333 4444 55555

F is a function that number x has been repeated in an ascending order f(x).


x : 1 2 3 4 5 6 7 8 9 10

f(x): 1 2 2 3 3 3 4 4 4 4


my function gets 'x' and gives 'f(x)' and it has to do it without array but it goes wrong in high numbers.

int main()
{
int n;
cin>>n;
int i=1,a=1;
if(n==1)
cout<<'1';
else{
while(true){
a++;
i=i+a;
if(i>=n)
break;
}
}
cout<<a;
return 0;


}

Answer
int f(int x) {
    return (x * (x + 1)) / 2;
}

int main() {
    int n;
    cin >> n;
    int left = 1, right = n;
    while(left < right) {
        int mid = left + (right - left) / 2;
        int val = f(mid);
        if(val >= n) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    cout << left;

    return 0;
}

Use binary search. Right now I am in mobile. I will add the explanation later if needed. Let me know if you don't understand anything.

Comments