 # UKP1 IUPC Editorial

UKP1

ujjk29

ujjk29

Easy-medium

## Prerequisites:

Basic Maths, Binary search.

## Problem:

You need to find all x for given y such that f(x)=y.

## Explanation:

Let us consider a number x. And suppose that we divide it by two exactly ‘a’ times, and then we would be left with some number ‘b’.

Then the result would be (b*(b-1))/2 + b*((2^a)-1).

As this equation is increasing for a fixed ‘a’ we can use binary search over ‘b’ to get values.
This can be also solved by finding solutions of above quadratic equation.

## Solution Code

Quadratic Solution
Using Binary Search Solution

2 Likes

Not able to understand
how you came up with above result

(b*(b-1))/2+b*((2^a)-1)

2 Likes

Consider a number in binary form. Let the number is 1101000
Then the f(1101000) = 110100+11010+1101+f(1101)
f(1101) can be calculated easily as it is odd.

Now we see pattern. Consider b=1101 then f(1101000) = b.4+b.2+b+f(b).
Remember b is odd and hence f(b)=b*(b-1)/2.

Now the summation of terms can also written in this form: b[1+2+4] = b = b[(2^3)-1].

Hence when number is divisible by exactly 3 times we write it as b*[2^3-1].
And this can be generalised to b*[2^d-1] when number is divisible by 2, d times.

3 Likes

Thanks

How this equation is increasing for fixed a…
Can anyone explain with example.
Thanks

I used a different approach .
Checked every possible b and for checking 2^a I used (n&n-1) , it gives zero only when n is some power of 2

1 Like How did you come up with this result? can you please elaborate this if else statement

if () condition is checking for overflow. If there is overflow then we put val = maximum possible value.