4 kyu
Count ones in a segment
650 of 3,288d0n14
Loading description...
Binary
Performance
Algorithms
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
Your solution being too slow is not a kata issue.
Note that inputs in this kata can be very large numbers, like
count_ones(189700847246574, 320377134968482). Your current solution cannot handle numbers this big. It is even written in the description.A hundred lines... But performance seems to be just fine: my program counted the number of all ones from 1 to 999999999999999999 instantly.
It was a very interesting kata, I liked it. Solved the task using permutations with repetition.
Scala translation
Nice kata, great to practice with, well done.
Heads up. Both left and right are included in the count. I wasted nearly an hour wondering why my result was off by a tiny amount
Unless description was changed:
This comment has been hidden.
D translation
PHP Translation. Please review and approve.
This comment has been hidden.
Approved
Go translation.
approved
Rust translation (author is inactive).
approved
Kotlin translation ready for review and approval.
approved
COBOL translation, please review carefully (author gone).
approved
help please Error: countOnes(52868585, 68127216) Expected: 214418586 Got: 214419282
Error: countOnes(143852667, 147469842) Expected: 47992140 Got: 47992820
Error: countOnes(239138, 747794) Expected: 5047947 Got: 5048667
Error: countOnes(439665, 651596) Expected: 2131572 Got: 2132156
Error: countOnes(780302205, 780695789) Expected: 5838166 Got: 5838918
but in my ide, i get expected for all of them, any help please? im working on c!!
Language?
c
It's strange you get the right answer in your IDE and not here. It would mean the C implementations differ, some difference in the compiler... I'm not an expert so I can't say for sure but I don't even know if that's possible. I guess there must be some difference somewhere (a variable with a different type or something like that). So I would suggest first to double check that, and also have a look here: Troubleshooting Your Solution. After checking it if you cannot find the problem you may post your code with a spoiler flag and someone may help you (with no guarantee). There are many ways to solve this kata so it's hard to help without more informations.
Thanks, i think '__builtin_popcountll()' that im using in part of the code maybe the source of this.
Great kata!
Call for help!Thanks!
In attempt:
Exit code : 139
Response received but no data was written to STDOUT or STDERR.
Hi. A problem with your code is not a kata issue. You'd rather post a question if you want help. Hopefully this can help you: Troubleshooting Your Solution.
This comment has been hidden.
Your solution is way too inefficient.
Your solution has
O(n)complexity, because you count all numbers in order. However, the range can be very big.Instead, try to decompose the problem into the following:
Great. Simply and deep in same time. Thanks.
Nice kata:)
In C, type of arguments should probably be
int64_toruint64_tsince their values are said to reach as high as ~2E+14, butintcan only contain ~2E+9.Fixed
C++ seems have the same problem.
This comment has been hidden.
This comment has been hidden.
If there wasn't a pattern, you would have to iterate all of them like you started doing in the code sample. I could tell you what the pattern is, but discovering it and translating it into code is where the fun in this kata is at. You should get started in looking for a pattern by ouputting the first few numbers in binary (for example, 0..15), leftpad them with with 0's to make 4 bits -- then see if you can recognize the pattern. Happy hunting.
C# Translation added.Please review and approve~
I note that the current c# large unit tests do not push beyond the bounds of long integers, and I believe that they should. (I had a good time implementing this in c# regardless.)
output
I noticed the range issue after reading a solution that does its logic entirely in longs and only converts to BigInteger in the return. It also returned 0 for inputs larger than half of long.MaxValue (probably because its logic breaks down in that case.) Thus, it seems flawed that we don't have at least one random test that pushes beyond what fits in a long. I note that the count for the range
[0, long.MaxValue]is almost32 * long.MaxValue.Approved some time ago
Please review and approve my Forth translation
Wow this was difficult. I tried it semi-brute force and the optimization took hours.
This comment has been hidden.
Cheating is bad ;-)
This comment has been hidden.
This comment has been hidden.
This question really has its difficulty, Must consider efficiency issues.
This comment has been hidden.
super fun and challenging
Java translation
Please review and approve.
Someone to approve this, please?
Approved. Minor mistake in initial code
thx²!! (corrected)
This comment has been hidden.
Thank you for approving my translation!
Function name in Python initial code is
countOnebut the correct name iscountOnes.Fixed
ok I'm stack with this even my code works well
Process was terminated. It took longer than 12000ms to complete"WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!" the point of this kata is to come up with an idea how to calculate the result very fast without even going through the sequence and it requires making some observations about binary numbers
good luck! =]
This comment has been hidden.
Gret one! Hard and satisfying. Took me hours. Trying to explain the algorithm is a least as difficult as finding it :p
Fantastic kata! This one really forced me to sit down with pencil and paper first to figure out my approach.
It sure takes some time and got me on paper as well until I found the pattern
Pretty happy with it
JS translation kumited, please approve :)
C++: Needs random tests
All test, except the last one, are random and checked with my solution, which was checked by brutal force. The tests are in vectors so that It is easier to make fair translations
I don't think you're interpreting the word "random" correctly.
It's not random if the test cases are fixed, they're called fixed tests. It'd be slightly better if the order of the tests are randomized, but you didn't, so it's effectively fixed tests.
Fixed tests can be hard-coded.
The correct way to make random tests in this case is to generate pairs of random inputs on the fly and compare user answer against reference solution (i.e author solution).
Please review the tests once again now =) thanks for feedback
Looks good now :D
I'm thinking about it sometimes... Generally random tests are considered a good practice because they can catch an error eventually. But each solution here is usually tested one time or at least not a lot, so the point of the random tests is to prevent cheating. It's unlikely that someone will run their inefficient solution for each test and hardcode the answers if there's a large number of tests and the inefficient solution is very bad for the given problem. So is there much difference after all?
Well, in this case large amount of random tests also serves as a way to benchmark code runtime/memory consumption. It's usually available in the submission results on other OJ (Online Judge) websites.
Also, edge cases. It often happens that author solution is revealed to be flawed after random tests are added ;-)
Wait, I suddenly discovered that this kata has performance requirements!
I think maybe you should mention it in the descriptions.
done=), thanks
A duplicate of https://www.codewars.com/kata/count-the-ones
Look at the examples in both, but you were right in case of similar names, so I changed mine a bit to make it more clear, thanks for noticing
Oh, right, this is different from that kata. Sorry for the bogus issue :)
Probably a duplicate. I'll check later but I remember something like this here.
If you find this kata and it will be truly similiar to this one, I will delete mine
https://www.codewars.com/kata/simple-fun-number-10-range-bit-counting But that one is without performance requirements, so it's OK.
Error for your submit tests:
Thanks for informing. I fixed it, sorry for newbie kata errors =)