I think there is a mindset issue at play here. Instead of thinking "Wow, that person is such an elite hacker, I wish I had been born with that talent." think of it as "Wow, it was amazing how they came up with that solution. I want to learn how they did it so I can do the same.".
Stated different, ask people their process. If they came up with a solution that was much better than yours, ask them how they came about it. It may look like they've magically came up with a solution, but they do have a mental process that brought them to it. Find out what it is, internalize it and make it your own.
No. They train. They study symptoms, and causes, and treatments. They learn about how symptom X is caused by disease Y, and is usually treated by medicine Z.
But medicine Z doesn't work in all cases, it's only 75% effective. So you might need to try medicine Z2 instead. etc.
And they they do this, over and over and over, adding in new knowledge of symptoms, treatments, effectiveness, etc. They do this on paper, and they do this in a controlled, supervised environments until they can demonstrate enough mastery to be able to demonstrate that they know enough of this body of knowledge of problems and solutions to be trusted to apply it on their own.
Programming is no different. Answers don't magically spring, unbidden, from some secret programming organ in your brain - you need to learn the established patterns for solving different types of problems. Then, you need to apply them to different situations.
Right now, you're frustrated because you don't have a very big 'bag of tricks' yet. You've only learned a couple of 'solution patterns'. You said that some problems are easy - right? Well, they're easy because you've already added those to your 'bag of tricks'. You've learned the patterns that solve those particular problems.
The ones that are hard? That's because you haven't learned those patterns yet. Once you do, they'll be easy too.
So, looking up solutions for how to solve these 'hard' problems isn't cheating - it's learning. You're learning new solutions.
As time goes by, your library of problem->solutions will get bigger and bigger, allowing you to solve more types of problems.
So, don't think of it 'ZOMG - I'm so dumb! I can't magically come up with the solution to this type of problem that I haven't encountered before!'
Instead, think of it as 'Hmm. That's interesting. Here's a new category of problem that I haven't solved before. The existing solutions that I have in my toolkit aren't solving it, so let's go learn a new solution pattern. Then I can add it to my toolkit for future problems.'
I'll continue learning. Getting problems right and watching those tests light up green on Codingbat is a very nice feeling. I do get genuinely upset and frustrated when I can't figure out a problem, though. I'm not sure whether that means I hate coding or like it deep down.
One hack I'd suggest for fulfilling the craving of doing things "from scratch" when you're frustrated at a particular problem is to go back to one you already solved, but pick some class or method or set of methods of Java's library you used and make your own version. New problem! Data structures can be the most common. Used a java.util.Stack object? Write your own Stack class. Instead of `int Integer.parseInt(String);`, write your own. Try a hash map when you're a little more experienced. Pretty much everyone with the hunger writes their own string class eventually (usually in C++). Or try to solve the whole problem again in a language that gives you less, like C. It's good practice for college and tech interviews too. Too boring? Waste of time? Good, you'll appreciate it's there next time so that you don't have to keep reinventing the wheel and can just use it as you go about inventing some new thing made of wheels. The only danger is if your appetite is totally consumed, you'll swing the other way always searching and waiting for the right set of already-built dependencies you just have to glue together, and even then you could just hope for a framework that does that, your tolerance for exerting any programming effort for 'boring' stuff will go away, and everything will be 'boring'. That's not a great state to be in if you have aspirations of building rather than simply using.
I get the same feeling, but I get it about plenty of other things.
I love coding, but I don't love it on a daily basis while I'm working, and I certainly don't love getting stuck on a problem I can't solve. I do love the moment I get it working, though.
As your knowledge increases, you'll gradually run into fewer problems that you can't solve in pseudo-code, but you're not SUPPOSED to be able to solve any problem in code when you start.
The mere fact that you even have a few ideas to try is testament to your aptitude.
Keep on trucking, you'll get there.
That's why I was asking for a problem. I need one that will tell me if I have the right brain wiring/mind. "If you can't do this without outside help in X minutes, you should quit learning to program." Not incredibly easy like FizzBuzz, but not incredibly difficult. Somewhere in the middle.