http://www.spoj.pl/problems/FP/

here is the link. Can anyone please give me the hint only that how greedy approach is following in this question ? It's strange to see how greedy is there in this question. just the hint of this. no code, nothing! thanks.

Recommended Answers

All 7 Replies

Because in the search for an answer, your algorithm should always favor the larger numbers, in the search for the password. Smaller numbers get lower priority.

http://en.wikipedia.org/wiki/Greedy_algorithm

how are you thinking to do it ? divisible by 9 means sum of digits is divisible by 9. okay ? then how are you thinking to do that ??

To be honest, this problem doesn't seem interesting to me. I did see that only 22% of the submissions, were good on this problem - so it's relatively low on successes.

What I like to do with a puzzle/problem is first, work through it by hand (perhaps with a simplified example of the problem first. After doing it with paper and pencil, a time or 3, I notice ways and then better ways, to solve it.

That makes the backbone of my initial coding effort's logic.

Since checking for a sum of nine among the numbers sounds efficient, perhaps that check, beginning with the largest numbers, would be a good place to start.

If you need the greatest numbers (of some kind), you still want to center your logic, around those largest numbers, for your search, imo.

If you were given a list of numbers, how would YOU find the greatest N of those numbers, whose sum adds up to 9, efficiently?

it has given that you have to k elements. so what exactly i can follow, that what i am not getting. i know greedy can work here, but how is it implementing. what have you thought ?

and the question you have asked in last line, i am thinking upon it. thanks

Look at the second example: you need two numbers from his "favorites", whose sum is divisible by 9.

So it's a problem of reading in the data, and juggling the favorite numbers in each case, to find the highest numbers, that are divisible by 9 when added together. Since reading in the data is a fixed amount of time, generally, it's the "juggling" of the favorite numbers that is the heart of the matter.

I was surprised to see that so many of the attempts turned in, had wrong answers. ;(

Kind of a shame this is such an uninteresting problem. Any light bulbs go off?

okay! i got that i need to read k elements from the set which make it divisible by 9. okay. but i need efficient one. why are you repeating that this is an unintersting problem ? and can you provide me the way to solve this question in the exact way ?

Yeah, probably could. But I won't, because it's a challenge, and just giving the answer removes all the challenge. No challenge, no fun!

If that problem is too difficult, why not start with easier one's, and work your way up? A lot of figuring out how to code up answers to these programming challenges, is to practice - it's a bit like swimming - you will never swim well, without getting into the water, and practicing your swimming.

Even the great Sherlock Holmes, was always learning things as he went from case to case, solving crimes.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.