programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Help me solve this with Divide and Conquer

Ranch Hand
Posts: 122
Hello guys, can you please give me an idea on how to solve this.. i believe i need Divide and Conquer method, maybe im wong..

I have to solve this:
x2+s(x)+200·x=N

N is given by the user, also A and B, which is the range of X.
but the range can be up to 1,000,000,000

lowercase baba
Bartender
Posts: 12565
49
can you explain what that means? I assume your "x2" means x * x, but I have no idea what s(x) would mean.

Kaspersky Ukshini
Ranch Hand
Posts: 122
Ohh im sorry.
yes, that means x*x.. and s(x) means the sum of the numbers in a number... thats easy, i already wrote that..
for example s(115) would be 1+1+5..

Ranch Hand
Posts: 10128
3
Still your question is not clear enough. What is that A and B you are referring to in your first post? Do you mean that x can be anywhere between A and B which could be 0 and 1,000,000,000?

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
well..divide and conquer generally means "pick some of the possibilities. Determine if the solution is in that set, or not. discard the the set you don't need. repeat."

A common example is guessing a number between 1 and 100. I will tell you higher or lower. How would you solve that?

What you need to do is figure out how YOU would solve it using your brain, pencil and paper. Once you can do that, and ONLY once you can do that, do you start writing code.

Kaspersky Ukshini
Ranch Hand
Posts: 122
Joe Harry wrote:Still your question is not clear enough. What is that A and B you are referring to in your first post? Do you mean that x can be anywhere between A and B which could be 0 and 1,000,000,000?

Yes, thats correct .. X will be numbers from A to B..

fred rosenberger wrote:well..divide and conquer generally means "pick some of the possibilities. Determine if the solution is in that set, or not. discard the the set you don't need. repeat."

A common example is guessing a number between 1 and 100. I will tell you higher or lower. How would you solve that?

What you need to do is figure out how YOU would solve it using your brain, pencil and paper. Once you can do that, and ONLY once you can do that, do you start writing code.

Thats what im asking help for... i know how divide and.conquer works, i just need some help how to properly implement it..

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
so again...How would YOU solve it with pencil, paper, and your brain?

Programming is not about writing code. it is about thinking through problems. Literally writing stuff down on paper. "first I would do this. Then I would do this".

then, you take those steps, and revise, them. explain in more detail how you do that step. Eventually, you get to the point where you could give those directions to a 10 year old child, and reasonably expect them to be able to perform the actions.

Only when you have that done should you consider writing a single line of code.

so, give us those steps you've written down.

Kaspersky Ukshini
Ranch Hand
Posts: 122
fred rosenberger wrote:so again...How would YOU solve it with pencil, paper, and your brain?

Programming is not about writing code. it is about thinking through problems. Literally writing stuff down on paper. "first I would do this. Then I would do this".

then, you take those steps, and revise, them. explain in more detail how you do that step. Eventually, you get to the point where you could give those directions to a 10 year old child, and reasonably expect them to be able to perform the actions.

Only when you have that done should you consider writing a single line of code.

so, give us those steps you've written down.

Dude, I honestly understand completely what you are saying, the thing is that I'm not asking for a code or a complete solution.. I'm asking help for the idea on how to solve it, writing it is easy, I know that...
The thing is that I have no idea...

Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??

Ranch Hand
Posts: 221
5
I have to go with Fred and Joe on this. I admit that I'm not the brightest crayon in the box, but based on the information you have provided, I still don't know what you are trying to solve for.

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Kaspersky Ukshini wrote:I'm asking help for the idea on how to solve it
and that is exactly what I am doing.

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Kaspersky Ukshini wrote:Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??

Maybe I mis-spoke. Don't diving your range into two halves.

instead, choose a number somewhere in the range. for example, say N is 1456, A = 0, B = 10.

What would you do?

Kaspersky Ukshini
Ranch Hand
Posts: 122
fred rosenberger wrote:
Kaspersky Ukshini wrote:Let's say I split the given range into two halfs.. how would I know in which half my 'X' (solution in the given range) is, so I can proceed into more splittings and get to my solution...??

Maybe I mis-spoke. Don't diving your range into two halves.

instead, choose a number somewhere in the range. for example, say N is 1456, A = 0, B = 10.

What would you do?

Got it!
I choose ONE number, if that number doesn't give me the exact result N, then I check if the result for that choosen number is BIGGER or SMALLER than the result I need (N)... if it's bigger, I set a new B, which would be my choosen nubmer in this case...and repeat it... is that correct?

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Kaspersky Ukshini wrote:Got it!
I choose ONE number, if that number doesn't give me the exact result N, then I check if the result for that choosen number is BIGGER or SMALLER than the result I need (N)... if it's bigger, I set a new B, which would be my choosen nubmer in this case...and repeat it... is that correct?

CORRECT!!! GOOD JOB!!!

Doesn't it feel so much better to figure it out yourself than to be told the answer?

Now...the next question becomes...how do you choose your one number?
also...if you choose a number and you KNOW it is too big, do you really need to set B to that number, or is there a slightly better choice?

Also note: This sort of method ONLY works if your results are ordered. I haven't completely convinced myself that given any number x, that x+1 is always larger, but I'm about 99% sure.

Master Rancher
Posts: 2045
75
And, of course, if there is at least one point for which the equation holds.

So, my first advice is: set s(x) equal to 0 for the moment, and test if the
equation, with given A, B and N, has a solution.

for x between 0 and 1.000.000.000, you would have that s(x) <= 81,
so the initial solution should be close.

Question: what to do with s(x) if x is not an integer? For instance: x = 2 / 3?

Greetz,
Piet

Kaspersky Ukshini
Ranch Hand
Posts: 122
All the time, I was thinking that all the formula is EQUAL to X, so that was freaking me out lol.... I noticed it was =N (which Is a fixed value once the user inputs it lol)

anyways, I need some help with this part:

does my N, in this case hold

-2,147,483,648 to 2,147,483,647

Just to make sure...

Piet Souris
Master Rancher
Posts: 2045
75
Well, you would have x^2 + s(x)+ 200x = x or

x^2 + s(x) + 199x = 0

which is nearly the given formula, with N = 0.

And whether your inputted N willl be between these values?
Depends on what you type in. Try typing 'javaranch' for instance ;)

Greetz,
Piet

Kaspersky Ukshini
Ranch Hand
Posts: 122
Doneeeeeeeeee!!!

I did it, thank you guyss !!!

 It is sorta covered in the JavaRanch Style Guide.