• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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'.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You shou‍ld 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.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Khusbu Sinha wrote:. . . There are `N'  boxes . . . each containing different number of balls. . . .
Are the numbers sequential? Are they in order?
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I haven't done any problem related to combinations/subsets of random numbers from an array object.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 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?

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.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Khusbu Sinha wrote:
Junilu Lacar wrote:  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?

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

Do you mean exactly once or at most once (possibly zero times)?
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I mean exactly once.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, do you know how to check if a number is a multiple of another? See the % operator in Java
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK. I am working on the problem now.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Khusbu Sinha wrote:. . . 'a' number of subsets.
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.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ Junilu
Yes. I got it. Thanks for the detailed explanation. I am implementing it.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your swap method does not work. You can't do it like that because parameters in Java are passed by value.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok. I have changed the method name to `smallestMultiple`.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote: 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.


Probably, my method to select random values is incorrect. It selects repetitive values per loop of sum calculation.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.



 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adding the following after Line 18, solved my problem and the program now runs correctly.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 Pass-by-value in Java. Can I get some related links/tutorials to help me understand it well.
 
Knute Snortum
Sheriff
Posts: 4288
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This article may help.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Khusbu Sinha
Ranch Hand
Posts: 117
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Knute
Thanks for the article.
@Campbell
What text editor would you suggest?
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On Linux, probably Kate. On Windows®, Notepad++. Enable the options for syntax highlighting, bracket matching, automatic indentation (1 tab → 4 spaces) and right margin.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!