Choosing random numbers of elements from an array and calculating their sum

I have to solve the following problem:

There are `N' boxes (0<=N<=1000) each containing different number of balls. The user has to input two random numbers `a' (a<N) and `b'such that 'a' no. of boxes are selected from the total `N' no. of boxes and the total no. of balls in those 'a' boxes is the minimum possible multiple of 'b`.

I have to write a method that takes the parameters as `N', `a' and` b' and returns the minimum possible multiple of 'b' as explained above.

Sample Test case:

Input:

No. of balls (N) = 5

The no. of balls per box = {1,2,3,4,5}

No. of boxes to select (a) = 3

No. whose minimum multiple is desired (b) = 5

Output:

10

Here the element (which represents the no. of balls in each box) 1,4,5 add to 10 which is the minimum possible multiple of 5 for 3 selected boxes in this case.

I am having problem in iterating over this array to get required combination of 'a' number of boxes which meet the above requirement. For loops fail here since the number of combination (selection) is not known before execution. Please suggest a suitable data structure/process for this problem.

There are `N' boxes (0<=N<=1000) each containing different number of balls. The user has to input two random numbers `a' (a<N) and `b'such that 'a' no. of boxes are selected from the total `N' no. of boxes and the total no. of balls in those 'a' boxes is the minimum possible multiple of 'b`.

I have to write a method that takes the parameters as `N', `a' and` b' and returns the minimum possible multiple of 'b' as explained above.

Sample Test case:

Input:

No. of balls (N) = 5

The no. of balls per box = {1,2,3,4,5}

No. of boxes to select (a) = 3

No. whose minimum multiple is desired (b) = 5

Output:

10

Here the element (which represents the no. of balls in each box) 1,4,5 add to 10 which is the minimum possible multiple of 5 for 3 selected boxes in this case.

I am having problem in iterating over this array to get required combination of 'a' number of boxes which meet the above requirement. For loops fail here since the number of combination (selection) is not known before execution. Please suggest a suitable data structure/process for this problem.

Khusbu Sinha wrote:

.

I have to write a method that takes the parameters as `N', `a' and` b' and returns the minimum possible multiple of 'b' as explained above.

There is a slight correction here: The parameters are the array (representing the no. of balls per box), 'a' and 'b'.

You should have given those parameters decent names, then you wouldn't have required that explanation; what about array intendedFactor and numberOfTerms?

Are you supposed to choose all the locations in the array at random? In which case I could have chosen three random indices and got 4+4+2=10. Please confirm whether your array contains 0.

I think you need to go and find a piece of paper and write down how you are going to do this. Don't even try with code until you have got an algorithm on paper.

Are you supposed to choose all the locations in the array at random? In which case I could have chosen three random indices and got 4+4+2=10. Please confirm whether your array contains 0.

I think you need to go and find a piece of paper and write down how you are going to do this. Don't even try with code until you have got an algorithm on paper.

Are the numbers sequential? Are they in order?Khusbu Sinha wrote:. . . There are `N' boxes . . . each containing different number of balls. . . .

Ok. I am updating the variable names to reasonable ones.

Yes, all the locations in the array have to be chosen at random.

The array may contain 0 and the numbers are not sequential. They can be any random number inside the array.

Yes, all the locations in the array have to be chosen at random.

The array may contain 0 and the numbers are not sequential. They can be any random number inside the array.

Do you know how to get “random” numbers out of a Random object? And don't do arithmetic with Math#random. I presume you have a maximum value for the numbers in the array.

Search my posts in this forum for__random ints toArray__ and you will find something useful. Are the numbers truly random, or are you insisting they be distinct?

Search my posts in this forum for

The numbers in the array are user input values. So, in that sense, they are `random' here.

By the way, I am unable to access that forum link.

By the way, I am unable to access that forum link.

I haven't done any problem related to combinations/subsets of random numbers from an array object.

My first step would be to distill the problem and get rid of the unnecessary "decorations" with boxes and balls.

My first crack at simplifying the requirements would be something like this:

Given an array of integers R with N elements. Each element of R is unique and can have a value from 0 to N, inclusive. Elements of R are not arranged in any particular order. This much seem pretty clear to me.

Here's where I'm not so clear. Are you supposed to be given a random number A that's less than N and another random number B? Then you're supposed to pick A elements from R at random then figure out the minimum possible multiple of B you can get from those A numbers?

Some clarifying questions: Do you have to use*all* of the A numbers you randomly pick from array R to find that minimum multiple of B? Can you use them only once or can I use each of them multiple times if I have to? Are you limited to the kind of arithmetic operations you can use to compute the minimum multiple? In your example of 1, 4, and 5 to calculate 10 as the minimum multiple of 5, the most obvious operation used there was just addition. That is, 1 + 4 + 5 = 10. So you can only do addition? What if the numbers don't add up to any multiple of B?

Let's take another example. What if R = {0..50} and A = 3 and B = 13. Then what if the three numbers I randomly picked from R are {1, 17, and 23}. How am I supposed to calculate a minimum multiple of 13 from these three numbers? What would be the output of the program in this case?

My first crack at simplifying the requirements would be something like this:

Given an array of integers R with N elements. Each element of R is unique and can have a value from 0 to N, inclusive. Elements of R are not arranged in any particular order. This much seem pretty clear to me.

Here's where I'm not so clear. Are you supposed to be given a random number A that's less than N and another random number B? Then you're supposed to pick A elements from R at random then figure out the minimum possible multiple of B you can get from those A numbers?

Some clarifying questions: Do you have to use

Let's take another example. What if R = {0..50} and A = 3 and B = 13. Then what if the three numbers I randomly picked from R are {1, 17, and 23}. How am I supposed to calculate a minimum multiple of 13 from these three numbers? What would be the output of the program in this case?

It isn't a link. But if you aren't using Random objects, it wouldn't have helped you.

So you have a small number of user‑supplied numbers. Do you know how to get numbers from the keyboard? That would be a start:-You can delete line 5 when you are confident the keyboard entry is working correctly. You have to import Arrays: write` import java.util.Arrays; `before the beginning of your class.

So you have a small number of user‑supplied numbers. Do you know how to get numbers from the keyboard? That would be a start:-You can delete line 5 when you are confident the keyboard entry is working correctly. You have to import Arrays: write

Junilu Lacar wrote:

Here's where I'm not so clear. Are you supposed to be given a random number A that's less than N and another random number B? Then you're supposed to pick A elements from R at random then figure out the minimum possible multiple of B you can get from those A numbers?

Yes. That is exactly what is wanted.

Junilu Lacar wrote: Some clarifying questions: Do you have to use

allof the A numbers you randomly pick from array R to find that minimum multiple of B? Can you use them only once or can I use each of them multiple times if I have to?

Each combination of A numbers randomly picked can be used only once.

Junilu Lacar wrote: Are you limited to the kind of arithmetic operations you can use to compute the minimum multiple? In your example of 1, 4, and 5 to calculate 10 as the minimum multiple of 5, the most obvious operation used there was just addition. That is, 1 + 4 + 5 = 10. So you can only do addition? What if the numbers don't add up to any multiple of B?

Yes, only addition is allowed here. In case, the numbers don't add up to any multiple of B, -1 should be returned.

Junilu Lacar wrote:Let's take another example. What if R = {0..50} and A = 3 and B = 13. Then what if the three numbers I randomly picked from R are {1, 17, and 23}. How am I supposed to calculate a minimum multiple of 13 from these three numbers? What would be the output of the program in this case?

Here the output would be -1.

Khusbu Sinha wrote:

Junilu Lacar wrote: Some clarifying questions: Do you have to use

allof the A numbers you randomly pick from array R to find that minimum multiple of B? Can you use them only once or can I use each of them multiple times if I have to?

Each combination of A numbers randomly picked can be used only once.

Do you mean

I mean exactly once.

Well, do you know how to check if a number is a multiple of another? See the % operator in Java

I hope you're not waiting on more tips. All these questions I have asked were meant to help you clarify what your program needs to do. To work with random numbers, use the java.util.Random class. See the Random.nextInt() method.

Practically everything you need to write the program to solve this problem has now been mentioned in this thread.

Practically everything you need to write the program to solve this problem has now been mentioned in this thread.

Yes, I am aware of the `%' operator in java and its usage in checking multiples. The only problem I am having is iterating over the array for 'a' number of subsets.

OK. I am working on the problem now.

Beware: that is going to go into exponential complexity and it will take a very long time to iterate every subset of a large array.Khusbu Sinha wrote:. . . 'a' number of subsets.

You don't have to do any complicated iterations over the array and there are no "subsets" to worry about (well, I guess there is a subset involved but that's again not much to worry about) -- forget all that business with the balls and boxes, that was just supposed to help you visualize the problem but I don't know if it only confused matters more for you. I already distilled the problem down to its bare essence.

What you can do instead is to shuffle the elements of the array as you pick them out. Say you had an array {1, 2, 3, 4, 5}. To pick out 3 random elements, you'd do this:

Pick a random index from 0 - 4 (the Random.nextInt(int) method allows you to do this). Let's say you get 2 from your random generator. So, R[2] is the third element, which is the number 3. Great, you have the first number picked out.

A random generator does not produce unique numbers though, so it's possible that it could return 2 again the next time you call nextInt(). But you've already picked R[2], so what do you do?

Well, before generating another random number, you can move the value you don't want to pick again to the end of the array, so you'd swap the values in R[2] and R[4]. Now your R looks like this: {1, 2, 5, 4, 3}.

So, to pick the next number, you'd just generate a random number from 0 - 3 because you have one less number to pick from now. Let's suppose that Random.nextInt() does indeed give you a 2 again. No problem, because we've already swapped the old value out the end, R[2] is now 5. So again, you move 5 to the end but this time the end of the list is at R[3]. Now your array looks like this: {1, 2, 4, 5, 3}.

You keep doing this as many times as you need until you've picked out A numbers. When you're done, the A numbers you randomly picked out will be the last A elements of R.

What you can do instead is to shuffle the elements of the array as you pick them out. Say you had an array {1, 2, 3, 4, 5}. To pick out 3 random elements, you'd do this:

Pick a random index from 0 - 4 (the Random.nextInt(int) method allows you to do this). Let's say you get 2 from your random generator. So, R[2] is the third element, which is the number 3. Great, you have the first number picked out.

A random generator does not produce unique numbers though, so it's possible that it could return 2 again the next time you call nextInt(). But you've already picked R[2], so what do you do?

Well, before generating another random number, you can move the value you don't want to pick again to the end of the array, so you'd swap the values in R[2] and R[4]. Now your R looks like this: {1, 2, 5, 4, 3}.

So, to pick the next number, you'd just generate a random number from 0 - 3 because you have one less number to pick from now. Let's suppose that Random.nextInt() does indeed give you a 2 again. No problem, because we've already swapped the old value out the end, R[2] is now 5. So again, you move 5 to the end but this time the end of the list is at R[3]. Now your array looks like this: {1, 2, 4, 5, 3}.

You keep doing this as many times as you need until you've picked out A numbers. When you're done, the A numbers you randomly picked out will be the last A elements of R.

@ Junilu

Yes. I got it. Thanks for the detailed explanation. I am implementing it.

Yes. I got it. Thanks for the detailed explanation. I am implementing it.

In my program, the random values selected are getting `repeated` per loop of the selection for getting the sum.

Also, my output varies per execution. It sometimes gives the correct answer and at other times, gives the wrong ones or gives run time exception. I feel something is wrong with my method to select values.

Please help me correct this program.

MinMultiple.java

RandomSelection.java

Also, my output varies per execution. It sometimes gives the correct answer and at other times, gives the wrong ones or gives run time exception. I feel something is wrong with my method to select values.

Please help me correct this program.

MinMultiple.java

RandomSelection.java

Your swap method does not work. You can't do it like that because parameters in Java are passed by value.

It's great that you're trying to use descriptive names. Now try to get better at choosing names that fit your intent.

Choosing a method name like`ballCount` (not `ball_count`) would be great except in this case it doesn't fit your intent. Because of that, line 88 makes no sense. The label you print is "The minimum possible multiple" yet your method name says it's returning a ball count. That's like the checkout lady at the grocery store telling you how many oranges you bought when you ask her how much money you owe.

Choosing a method name like

Your implementation of the algorithm I described before is difficult to follow but it definitely is not right. I'm not following how calling the `multiple` method in a loop can result in different values being returned and added to that list on line 18. It doesn't seem like you have the algorithm clearly understood yet and that's reflected in the incoherence of the code.

Ok. I have changed the method name to `smallestMultiple`.

Junilu Lacar wrote: I'm not following how calling the

multiplemethod in a loop can result in different values being returned and added to that list on line 18. It doesn't seem like you have the algorithm clearly understood yet and that's reflected in the incoherence of the code.

Probably, my method to select random values is incorrect. It selects repetitive values per loop of sum calculation.

This is one of the outputs of this program that prints the correct answer `10'.

Enter the no. of boxes: 5

Enter the number of balls per box: 1 2 3 4 5

[1, 2, 3, 4, 5]

Enter the number whose multiple you want: 5

How many boxes do you want to select? 3

4 3 3

4 2 2

1 4 1

2 2 2

5 2 1

2 4 1

3 1 2

2 4 2

4 4 2

5 4 1

The minimum possible multiple = 10

>

Here, as we see, the values per row (i.e. per loop of sum calculation) are repeated which should not happen. I am not able to figure out the source of its `repetitive` nature.

Enter the no. of boxes: 5

Enter the number of balls per box: 1 2 3 4 5

[1, 2, 3, 4, 5]

Enter the number whose multiple you want: 5

How many boxes do you want to select? 3

4 3 3

4 2 2

1 4 1

2 2 2

5 2 1

2 4 1

3 1 2

2 4 2

4 4 2

5 4 1

The minimum possible multiple = 10

>

Here, as we see, the values per row (i.e. per loop of sum calculation) are repeated which should not happen. I am not able to figure out the source of its `repetitive` nature.

There's really no need to have a random generator as a local variable of a method. A single static declaration at the class level is sufficient. The name `rand` is a very common one used for this purpose. I would just use this variable directly where I need a random number.

Well, a loop is the most common way to repeat something in a program so maybe you should start by looking at which loop that output is coming from.

I have updated my multiple method using *List* to generate a set of non-repeating random values per iteration of the* for loop*. This solves the problem of duplicate values but my program gives the wrong answer as the minimum multiple. Please help me find out what's wrong in the code to find minimum multiple from the list of multiples.

Adding the following after Line 18, solved my problem and the program now runs correctly.

As posted, your code is still horribly formatted, like you just randomly indent it

Are you not using an IDE that can autoformat your code? I don't understand how you can even stand to read code formatted like that. I certainly can't.

Are you not using an IDE that can autoformat your code? I don't understand how you can even stand to read code formatted like that. I certainly can't.

Well, I have Dr.Java and Eclipse as IDEs in my PC and am currently using Dr. Java because I find it simple to use. I guess I need to switch to Eclipse (for auto-formatting) if my code format is annoying.

Junilu Lacar wrote:Your swap method does not work. You can't do it like that because parameters in Java are passed by value.

I am not able to understand this concept of

This article may help.

No, I would suggest you get a decent text editor and learn to do formatting by yourself. IDEs are not there to do what you don't know what to do. They are there to do what you already know how to do faster.

@Knute

Thanks for the article.

@Campbell

What text editor would you suggest?

Thanks for the article.

@Campbell

What text editor would you suggest?

On Linux, probably Kate. On WindowsÂ®, Notepad++. Enable the options for syntax highlighting, bracket matching, automatic indentation (1 tab → 4 spaces) and right margin.

I think you're missing the point by asking for a specific text editor. The point is that you need to learn how to format your code properly, it doesn't matter what editor you use. If you must have a recommendation, you can easily search for best programming text editors

This thread has been viewed 750 times.

All times above are in ranch (not your local) time.

The current ranch time is

Oct 17, 2018 08:47:06.

The current ranch time is

Oct 17, 2018 08:47:06.