eli delpierli - 8 months ago 75

C++ Question

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 Source

```
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.