- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Bear Bibeault
- Jeanne Boyarsky
- Tim Cooke

Sheriffs:

- Knute Snortum
- Junilu Lacar
- Devaka Cooray

Saloon Keepers:

- Ganesh Patekar
- Tim Moores
- Carey Brown
- Stephan van Hulst
- salvin francis

Bartenders:

- Ron McLeod
- Frits Walraven
- Pete Letkeman

posted 1 year ago

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

Ranch Hand

Posts: 120

1

posted 1 year ago

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

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'.

posted 1 year ago

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.

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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.

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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.

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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

posted 1 year ago

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?

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

Yes. That is exactly what is wanted.

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

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

Here the output would be -1.

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.

posted 1 year ago

Do you mean*exactly* once or *at most* once (possibly zero times)?

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

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

I mean exactly once.

posted 1 year ago

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

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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: 120

1

posted 1 year ago

OK. I am working on the problem now.

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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.

posted 1 year ago

- 1

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

@ 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.

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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

posted 1 year ago

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

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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

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.

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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.

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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: 120

1

posted 1 year ago

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

posted 1 year ago

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.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Khusbu Sinha

Ranch Hand

Posts: 120

1

posted 1 year ago

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: 120

1

posted 1 year ago

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.

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

posted 1 year ago

- 1

This article may help.

All things are lawful, but not all things are profitable.

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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: 120

1

posted 1 year ago

@Knute

Thanks for the article.

@Campbell

What text editor would you suggest?

Thanks for the article.

@Campbell

What text editor would you suggest?

Campbell Ritchie

Marshal

Posts: 60895

190

posted 1 year ago

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

posted 1 year ago

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

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!