• Post Reply Bookmark Topic Watch Topic
  • New Topic

Find the last number along with the minimum operations to get a particular number from 1 to n  RSS feed

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm trying to find the last number with random operators of '+' or '-'.
The number starts from 1 to n and I cannot enter which operator I need.

For example, the result value is 15 and counts from 1.

1+2+3+4+5 = 15

From 1 to 5, they make 15 when I add all. So, I need to print 5.

However, the operator can be minus, as well.

For example, the result value is 12.

Then, -1+2+3+4+5+6-7 = 12

There are two minuses, but I need to get 7.

I need to implement like above, but I'm confused which algorithm I need.




I tried like this, but the result depends on which numbers are taken. So, I got different numbers everytime.
 
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you please make your request more clear? Give us like 5 examples and explain what the desired output is for each. I will try to make more sense out of what you wrote, but it's hard to do.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jiyoung Kim wrote:I'm trying to find the last number with random operators of '+' or '-'.
The number starts from 1 to n and I cannot enter which operator I need.

1+2+3+4+5 = 15

Then, -1+2+3+4+5+6-7 = 12

There are two minuses, but I need to get 7.


Why in the first example you need 15 and in the second you need 7.
What do I as a user need to introduce? Do I introduce the number 7 and the program has to show us a series of operations like 1...2...3...4...5...6...7=7?
 
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That isn't a programming exercise, but manipulation of arithmetic. Start by working out how you would solve it without a computer.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
...and welcome to the Ranch
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I explained a little bit more what I want to do.

The implementation I want to do is like below.

Enter the number: 12

Then, there is a method for checking the operation.

checkOperations(int number) {
    // something
}

check from 1 to n to get 12 with the operator, '+' or '-'

So as I mentioned,

-1 + 2 + 3 + 4 + 5 + 6 - 7 = 12

This is a minimum operation to get 12. So the result returns 7 without an operator.

In another example, enter the number, 15. Then,

1 + 2 + 3 + 4 + 5 = 15

This is the minimum operation to get 15, so returns 5.


I tried to find the last number of the operation to get my input number.
I thought that I need to calculate the operation with random operators, but the issue is that the result value is different because of the random operator.
Sometimes, it takes '+' or '-'. So, it can be 7 or 20 and so on.

I'm not sure how to figure out the operator if I don't use random keyword.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
random isn't a keyword.
You are still trying to think how you are going to do it, rather than what you are trying to do. Until you can write instructions on paper, you will not manage what you are trying to do.
And you are not using consecutive numbers from 1...n, as you think. You are using consecutive numbers from 0...n, which is why you can start with −1. That is really 0 − 1.
I suggest you start by working out the formula for the sum of consecutive natural numbers up to n, e.g. 0...6, 0...7, 0...8 etc. What are those totals. Also work out what happens when you change one of the + signs to a −.

And don't write any code.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:. . . consecutive numbers from 0...n, . . . .

To me it looks like it can start with any number and go to any number, which makes the problem really difficult.
 
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, if you think about it, it is not that hard.

First of all, one needs to know the formula for the sum of 1, 2, 3, ..., N by heart, but we all do, don't we?  

Then if you change the sign of any number in that series, the total sum decreases by an even number (why?).
Lets denote the sum 1 + 2 + ... + n with Sn.

Let's take the outcome of 12 as an example. We know thar S4 = 10, too low, so the next candidate is S5. But that sum is 15, and the difference with 12 is uneven. So S5 is impossible. Next xomes S6, being 21. The difference with 12 is again uneven, so S6 is also out of the question. S7? Well, the delta is 28 - 12 = 16, even and that can be formed by changing the signs of 1 and 7, or 2 and 6, or 3 and 5. Check: 1 - 2 + 3 + 4 + 5 - 6 + 7 = 12. So we have 7.

See the pattern? We only have to derive the general algorithm out of it. What if -12 is given?
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Well, if you think about it, it is not that hard.

Let's take the outcome of 12 as an example. We know thar S4 = 10, too low, so the next candidate is S5. But that sum is 15, and the difference with 12 is uneven. So S5 is impossible. Next xomes S6, being 21. The difference with 12 is again uneven, so S6 is also out of the question. S7? Well, the delta is 28 - 12 = 16, even and that can be formed by changing the signs of 1 and 7, or 2 and 6, or 3 and 5. Check: 1 - 2 + 3 + 4 + 5 - 6 + 7 = 12. So we have 7.

See the pattern? We only have to derive the general algorithm out of it. What if -12 is given?

This really simplifies things! So we just have to program something for Target number = n*(n+1)/2 -2*(sum of necessary positions). We need an algorithm that will iterate and check that S(i) - Target number % 2==0 and return i when true.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sergiu Dobozi wrote:. . . makes the problem really difficult.
As Piet Souris has explained, it is a much easier problem than you thought.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:. . . What if -12 is given?
I would say that you confine yourself to natural numbers (ℕ or ℕ₀, because I am sure that 0 is a natural number), so −12 would not be permissible.
I would also say that you don't calculate the total of 1...n, but as I said earlier, 0...n. That means you can confine yourself to addition and subtraction (binary operators) and do not need to apply a sign‑change operator (=numerical negation, =uminus, =unary minus) to the 1. The total will obviously be the same.

If you permit all integers (ℤ), you can get 12 easily as the sum of −2...5.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Piet Souris wrote:. . . What if -12 is given?
I would say that you confine yourself to natural numbers (ℕ or ℕ₀, because I am sure that 0 is a natural number), so −12 would not be permissible.
I would also say that you don't calculate the total of 1...n, but as I said earlier, 0...n. That means you can confine yourself to addition and subtraction (binary operators) and do not need to apply a sign‑change operator (=numerical negation, =uminus, =unary minus) to the 1. The total will obviously be the same.

If you permit all integers (ℤ), you can get 12 easily as the sum of −2...5.


The program can test if the number the user entered is negative or positive. So if the user enters -12, the program will have to find the difference between numbers -1 and -n.
The formula for the sum of -1, -2, -3....-n is just -n*(n+1)/2. For target number -12 the program should still come up with the following operations, using the same logic Piet proposed: 1-2-3-4-5-6+7.
 
Piet Souris
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sergiu Dobozi wrote:The program can test if the number the user entered is negative or positive. So if the user enters -12, the program will have to find the difference between numbers -1 and -n.
The formula for the sum of -1, -2, -3....-n is just -n*(n+1)/2. For target number -12 the program should still come up with the following operations, using the same logic Piet proposed: 1-2-3-4-5-6+7.

Indeed. I would formulate it like this: solve for +12. You can then change all operators if you like, but it doesn't matter for the outcome (7).
 
Piet Souris
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Piet Souris wrote:. . . What if -12 is given?
I would say that you confine yourself to natural numbers (ℕ or ℕ₀, because I am sure that 0 is a natural number), so −12 would not be permissible.

I agree that 0 is a natural number. It is all too often that I look into my wallet and see 0 euros.

But look at the opening post. It is about the series 1 + 2 + ... + n, in which zero or more plusses are replaced by minusses (is that correct English?). Therefore it is quite possible that -12 is given.

Campbell Ritchie wrote:
I would also say that you don't calculate the total of 1...n, but as I said earlier, 0...n. That means you can confine yourself to addition and subtraction (binary operators) and do not need to apply a sign‑change operator (=numerical negation, =uminus, =unary minus) to the 1. The total will obviously be the same.

If you permit all integers (ℤ), you can get 12 easily as the sum of −2...5.

Can you elaborate this a little? I have these two problems:

1) the answer when given 12 is 7. How do you derive this from the series -2 + -1 + 0 + ... + 5?
2) how do you apply this method when say 17 is given instead of 12?
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:. . . 1) the answer when given 12 is 7. How do you derive this from the series -2 + -1 + 0 + ... + 5?
I meant that −2...5 add up to 12. You are right that there are seven operators in that series. I obviously didn't read the original post properly.
2) how do you apply this method when say 17 is given instead of 12?
0...6 (=21) with a − before 2. You do not have to include negative numbers in the series. I was saying that the idea was to confine oneself to ℕ₀. One would probably regard −2...5 as cheating.

Plusses are of course a kind of knickerbocker, but yes, your grammar is correct. We call numbers odd and even. It is only the programming that is uneven on this website
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Well, if you think about it, it is not that hard.

First of all, one needs to know the formula for the sum of 1, 2, 3, ..., N by heart, but we all do, don't we?  

Then if you change the sign of any number in that series, the total sum decreases by an even number (why?).
Lets denote the sum 1 + 2 + ... + n with Sn.

Let's take the outcome of 12 as an example. We know thar S4 = 10, too low, so the next candidate is S5. But that sum is 15, and the difference with 12 is uneven. So S5 is impossible. Next xomes S6, being 21. The difference with 12 is again uneven, so S6 is also out of the question. S7? Well, the delta is 28 - 12 = 16, even and that can be formed by changing the signs of 1 and 7, or 2 and 6, or 3 and 5. Check: 1 - 2 + 3 + 4 + 5 - 6 + 7 = 12. So we have 7.

See the pattern? We only have to derive the general algorithm out of it. What if -12 is given?



Thanks for your answer. I coded by following your instruction, and I got the correct answers. I understood the pattern, but I still don't figure out how to prove clearly like you're saying.
I got that I need to add the numbers until sum is bigger than 12. But, I'm confused why it should be even. The operators don't matter, but I don't have an idea why the even number between two differences is satisfied with this condition.
Please give me some explanations to make me understanding more clearly.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I merged your stuff with the following thread. I hope that is okay by you.
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a question about one algorithm to find the maximum number using + or - at minimal times.
For example, I have a value of 12, then the number counts from 1 to n. 1 2 3 4 5 ... n
The operator can be + or -, but I need to find the number that is satisfied with.

In this case, the operators are something like that. -1+2+3+4+5+6-7 = 12.
This equation is satisfied with 12 and 7 is the maximum number. I think that it doesn't matter whatever operators comes on.
However, I don't understand clearly why the algorithm below is working properly to find the number.

*Algorithm*
Add the numbers from 1 until its sum is bigger than 12. In other words, 1+2+3+4+5=15
15 is bigger than 12, and get the difference between these two numbers. 15-12=3 3 is odd, so it keeps going.
1+2+3+4+5+6=21 and 21-12=9. 9 is still odd, so add the next number. 1+2+3+4+5+6+7=28 and 28-12=16
16 is even, so calculation is done. So, the result will be 7.

I programmed by following this concept, and I got the answer I want.
So, the algorithm is correct, but I don't have an idea how to know the even number of differences between two numbers will be the answer.

Do I just need to memorize the algorithm approach?? Please give some hints to how to figure it out.
Thanks.
 
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jiyoung Kim wrote:
Do I just need to memorize the algorithm approach?? Please give some hints to how to figure it out.


Well, obviously, memorizing it is not very useful, as this logic is just unique to this problem. 

As for hints, well, hmmm, think about what you will be doing. You will be changing (one or more) operators from positive to negative. What will happen? Obviously, one thing that will happen is that the sum will be lower... but is there something else? Look at the math, and you should figure out why the difference must be even.

Henry
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like you simply split off (or duplicated) this question from here...

https://coderanch.com/t/672251/java/Find-number-minimum-operations-number

Please don't do that, as now you have two topics that are discussing the same thing.
Also, Piet explained it in the math for you in the other topic.

[EDIT: post edited as the split off topics mentioned has been merged]

Henry
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please search this forum and this one because the same problem has come up before.
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Henry Wong wrote:. . . now you have two topics that are discussing the same thing. . . . Henry
In which case we can join the two topics back together.


I'm totally ok with that.
Yes, the topic is the same but I'm confused with the concept.
I don't fully understand why even numbers are only satisfied with this algorithm.
I figured out what if the result value is even or odd, the differences between two numbers should be even to be satisfied with. That is why i asked for the concept of this algorithm to make clear.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't know what the algorithm is. Recently our undergraduates were looking at the Collatz conjecture and trying to program an app which counts how many steps it takes to get from n to 1. So I referred them to the Wikipedia link above and asked them what algorithm there is to calculate steps. I then had to point out that there isn't an algorithm in that link at all, which means there isn't such an algorithm. I don't know whether there is such an algorithm for your problem. Did you find anything when you searched the fora as I suggested yesterday? Please search the whole Net for mathematical websites and see whether there is such an algorithm. Please see if you can work out an algorithm on paper. What you are doing is calculating a triangular number (also try Maths is Fun link to the same and Wikipedia:Triangular_number). Start by calculating the smallest triangular number not less than your desired total and seeing what the difference is. Also rather than adding 1+2+3+4+5, try 0+1+2+3+4+5. That might make 12 easy to find . I think you will have no difficulty getting 11 or 13 out of that sequence, so I can't see why you said anything about even numbers.
 
Campbell Ritchie
Marshal
Posts: 56608
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, I think that you will find the solution will get easier and easier once you start thinking about triangular numbers
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Actually, I think that you will find the solution will get easier and easier once you start thinking about triangular numbers



Yes, it's not the algorithm as you said. It's math.
I will try to find the solution based on your replies.
 
Piet Souris
Master Rancher
Posts: 2045
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Jiyoung

if sum1 = a + b
and sum2 = a - b,

then sum1 - sum2 = 2b, and therefore even.

Now, if we have S5 = 1 + 2 + 3 + 4 + 5, and we change the sign of one digit in this series, the difference is an even number. So it is impossible to obtain 12 by changing zero or more signs in S5, since the difference 3 is an odd number.
 
Jiyoung Kim
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:@Jiyoung

if sum1 = a + b
and sum2 = a - b,

then sum1 - sum2 = 2b, and therefore even.

Now, if we have S5 = 1 + 2 + 3 + 4 + 5, and we change the sign of one digit in this series, the difference is an even number. So it is impossible to obtain 12 by changing zero or more signs in S5, since the difference 3 is an odd number.



I understood the concept now. The difference between two sum and two difference of the combination of even/odd, even/even, odd/odd, odd/even should be the even.
So, that's the reason why I need to check if the difference between two numbers is even. I got it..

Thanks for your reply.
 
Ranch Hand
Posts: 1143
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jiyoung Kim wrote:
I understood the concept now. The difference between two sum and two difference of the combination of even/odd, even/even, odd/odd, odd/even should be the even.
So, that's the reason why I need to check if the difference between two numbers is even. I got it..

Thanks for your reply.


I'm curious... have you made any progress on this?
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!