r/learnjava • • Jan 26 '16

Unsolved Problem with a simple Algorithm.

Hi guys.

Pre:

A friend of mine gave me this and told me to use the console & the Scanner class.

Add together numbers until you come as close to 1.000(high&low) as possible, BUT IF two numbers are equally close to 1.000, choose the highest one.
The first number you write in to the console should be the number that tells how many numbers you will put in.

For an example.
I will put in 4 numbers in the console, (4, 900, 500, 498, 4)
If you add 500 with 498, you will get 998. That is close to 1.000,
but if you add 500 with 498 and 4, you will get 1.002.
998 & 1002 are equally close to 1.000, so then I need the program to choose the 1.002 and not the 998.

The problem I have is the Algorithm. How do I do this?
I can count every number I put together and do it while the sum are under 1.000, but then I will miss the 1.002.
I know that I can use the Math.max to compare 2 sums to see if they are equally far away from 1.000 and then choose the biggest of them.
But yes, I don't understand how you should think here.

This is what i have done right now, it just add all numbers you put in together, and as I said, the first number you write in the console will just tell the program how many numbers it will be put in.

So the question is, how do you think when it comes to this?
What goes in your head when you try to write the algorithm. You have any solution or help?
Thanks.

public class Main {

    public static void main(String[] args) {

        int numbers = 0, count;
        Scanner scn = new Scanner(System.in);
        count = scn.nextInt();

        while (scn.hasNextInt()) {
            numbers += scn.nextInt();
            count--;

            if (count == 0) {
                System.out.println(numbers);
            }
        }
    }
}
0 Upvotes

9 comments sorted by

View all comments

0

u/[deleted] Jan 26 '16

[deleted]

0

u/[deleted] Jan 26 '16
  1. I mean of course 1000 (one thousand).

  2. I believe I need to find all permutations, or do I?
    I dont think there are another way then try all the variations to see whats closest to 1000.

Like in the example, if my 4 numbers would be 500, 498, 400 and 4. Then without the variations I wouldn't find 1002, only 998 (500+498) I think.

0

u/[deleted] Jan 26 '16

[deleted]

1

u/[deleted] Jan 26 '16

Yes.
Like /r/bilal132 said, this is a power-set, I need to collect all numbers that comes in (a, b, c, d), then add in variations (a, a+b, a+b+c, a+b+c+d, a+c, a+d and then take b... and so on).

I think I need to use hashSet? Set? Dont think its a good idea with ArrayList.
I cant find any examples that are close to this one, something that should give any code/tutorial. Will read more about Sets.

Thanks.

0

u/[deleted] Jan 26 '16

[deleted]

1

u/[deleted] Jan 27 '16

That is a good thing, that it don't allow duplicates.
I will guarantee that the user only puts in Integers under 1000 in value.
Now I need to read more about Set and see how it works, thanks.