5 kyu
Is my friend cheating?
6,137 of 18,221g964
Loading description...
Fundamentals
Mathematics
Puzzles
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.
This comment has been hidden.
As previously reported there, it is unclear if
aandbmust be distinct. In C and OCaml at least, the author's solution returns(3, 3)forn = 5(1 + 2 + 3 + 4 + 5 = 15, 15 - 3 - 3 = 3 * 3 = 9).Wow, a really good kata!
VERRY minor issue, in the java version in this kata, the List class is not imported, and as such gives an error, can be solved by adding: import java.util.List;
Wonderful kata! I just love math puzzles
method name removNb seemed unnecessary, any reason you didn't name it something clearer like removeNumbers?
Amazing kata! It took me ages to pass the tests for large numbers. And when I checked out the solutions, I couldn’t believe my eyes, so simple!
why this is wrong n = 103: expected [ [ 486, 10 ], [ 10, 486 ] ] to deeply equal []
This comment has been hidden.
There is no errors in the tests. Timing out is not an issue.
Any idea what the problem is?
See if this helps: https://docs.codewars.com/training/troubleshooting#timeout
Alright, thank you both for your help. I'm working on it now, learning some new commands I've seen in other people's solutions before
Same thing happened to me. Looks like two order iteration is too much to pass the 10th test because n is such a large number. I think you should try reducing the number of iterations. When n is big, there are a lot of combinations you don’t really need to consider. This will make your algorithm more efficient.
Very nice kata, well done.
What are we supposed to return for if there are no values (in C#)? new long[0];? List<long[]>{ new long[0] };?
I got all my successful cases working, but the null ones I'm not sure what they're asking for.
It should return
new long[0]. However, your code will not pass large numbers because it will iterate all combinaions ofaandbfrom 0 up ton.There exists a formula which only requires an O(N) complexity.
Nim tests are broken, all tests pass, but solution is rejected because of "Exit Code: 1"
Can you paste your solution?
I already found that my solution is wrong. But it seems that any solution "passes" the tests.
fixed here
Tricky, 5 hours in front of my laptop hahaha, but that @subtalon said helped me to solve it in 5 minutes. It is not an algorithm problem at all, when you try it as an algorithm at all the code will be inefficient and the time will exceed the allowed to accomplish. It's better to understand it in a math way.
I get these error messages in c#: src/Solution.cs(15,26): error CS1026: ) expected src/Solution.cs(15,32): error CS1002: ; expected src/Solution.cs(15,32): error CS1513: } expected src/Solution.cs(19,7): error CS8803: Top-level statements must precede namespace and type declarations. src/Solution.cs(20,3): error CS1022: Type or namespace definition, or end-of-file expected src/Solution.cs(21,1): error CS1022: Type or namespace definition, or end-of-file expected If I copy and past the code into VS it works I can run it without error. But not here
You are using
list.Add([1, 2]);syntax for creating along[]. This is a Collection expression and this language feature was introduced with C# 12. Codewars currently only supports C# 10 so you need to use a different syntax to create the array.You can support this Github issue to maybe prioritize an update of the language version.
Yes it worked to change that, and the test passed. Thank you!!!
Hey you who is trying to solve this, non spoiler-ish tips:
both tips are unrelated.
This comment has been hidden.
did it myself. turns out i'm not all that dumb. i just had to write it down on paper.
Well, thank you for reminding me that basic advice, turned out that was super easy after all.
This comment has been hidden.
Your first step should be eliminating
ar. There are better ways for every case where it is used.The second step is finding a way to get
b(orjin your case) without a nested loop.I'll put more info in a spoiler comment.
This comment has been hidden.
after finishing, I felt dumb with the polynomial i divised...
Tried 3 different algorithms, each one build differit, but same timeout error... Pretty hard this kata, but a good one
It is so challenging yo!
C#: method name should be
PascalCase(Please refer to implementation of backward compatibility here )Whew, that was hard
im having timeout for all time im trying to sumbit this kata
This is almost certainly because your code is inefficient. In this kata there are several steps which you could reduce to closed-form solutions; if you're calculating the sum of all numbers from 1 to n by looping through and adding them, for example, you can do that in a single step instead. Similarly if you're testing every value from 1 to n against every other value from 1 to n, think about how at least one of those loops could instead become a calculation. Exercise your algebra.
This comment has been hidden.
After several hours of torment with double-passing, all sorts of squeezing intervals of variables, an elegant solution dawned on me. Thank you, g964. I used to hate your katas)
I'ts always you, g964, it's always you lmao. I'm having a hard time here because of timeout, this is incredible!
g964 kata, great kata, i think i would do it in 2 minute, and so i did, but only after 8 test timeout, twist is nice, after all math is beautiful!!
Thanks!
This comment has been hidden.
It would be kind to fork the Rust kata, I have no time for that... NB: Cheating is forbidden, you could be banned:-)
This comment has been hidden.
This was really interesting and i learned a new way of solving problemas. It took me a few hours to solve this one. Writing the equation down really helped me! Thanks everyone for the hint
This is one of the most satisfying katas I've ever solved
Thanks!
for removNB(26), {1, 175} is not a valid solution but should be because the total of all numbers in the sequence is 351, and 351 - 1 -175 == 175 * 1
but the answer doesn't pass the test.
That's because 175 is not part of the
1 to 26sequence."A friend of mine takes the sequence of all numbers from 1 to n (where n > 0)."
Inclusive or exclusive?
->
clearly inclusive, no?
No, not clearly.
had the same question and only reason I look into comment section right away. Thanks for asking and the reply. For me it is not clearly.
You can't find the sum(n)-(a+b) == (a*b), (as the problem is saying) if you are not including the n, this should be the first thing you would look into when you start solving this kata. Idk why would you ask this.
This is a nice problem, I am stuck with how to make my code faster... Anyone have any suggestions for me? Writing in swift
This is not a algorithm problem as much as it is a math problem. Perhaps having a hint left here would have helped, enjoyed the challenge though.
Yea, I think most people here are here for coding/programming, not mathematics.
This comment has been hidden.
Your solution is O(N^2). There exists a formula that can help you solve the problem with just O(N) time complexity. (1-time iteration)
JS translation with adding more random big tests
Thanks! Approved.
Ruby translation for upgrading to 3.0
I get task wrong, aren't I? In example sum of all elements from 1 to 26 is 325, if a and b equal 15 and 21, sum of sequence without a and b would equal 289, while 15*21 = 315 which is wrong in the way I get this
I am struggling with the same issue, have you solved it?
This comment has been hidden.
It actually is, no idea how I didn't notice that, thanks a lot!
My Go code works fine, it has a time complexity of O(n^2) (which is the best I could do) and passes the basic cases but times out when trying to submit. Quite frustrating.
Edit: I optimized the code which now is O(nlogn) I think. It works and passes all the submit tests in less than 2000 ms.
how?
This comment has been hidden.
I like how we are told to return an empty array if there are more than one solution and return "nil" if there is no solution but we acctually dont need to do that
Factor translation issue.
Test code has:
Calling
to-arrayon the output of the user function will give very cryptic error messages if the user does not return an sequence of sequences, due to an error on his side:which is unnecessary difficult to diagnose
Consider either a more robust implementation of
to-array, don't use it all, or introduce custom error handling.@Bubbler is the Factor translator and it seems that he has left CW. If you have enough time and the desire to better this translation it would be kind to do it.
Sure, I will give it a shot
Nim translation fixes
approved
About two months ago, I had no idea how to code. I cannot believe that I solved this today. Excellent kata!
You are amazing
After I've solved it, I can't believe I hate math even more, whoa...
n = 1000003: expected [ [ 550320, 908566 ], [ 908566, 550320 ], [ 559756, 893250 ], [ 893250, 559756 ] ] to deeply equal [ [ 550320, 908566 ], [ 559756, 893250 ], [ 893250, 559756 ], [ 908566, 550320 ] ] Just have this issue where I have to sort result even tho it's technicaly right but order is wrong?
In kata description it is written:
[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or ...will be sorted in increasing order of the "a".So you need to sort your returned array according to first element, yes.
you're right, guess I need to improve my reading skills lol
how do you even get it to work for this such big numbers. my code only works for smaller numbers. perhaps i will really need a spoiler on that. i will be glad if you can put me through.
My program works perfectly when tested, but fails just one test all because of the timeout issues. I feel down, after racking my brain to put down a code that works fine only to be rejected due to timeout issue.
The timeout is caused by your code being too slow, not a kata issue. Also, there are more tests, your code times out with some test and it halts the execution of further ones.
Yeah, I guess so.
You probably have a quadratic time solution ! You can solve this only looping through it once and have it be linear time.
For me is the same, I have a quadratic solution but so far I'm not being able to find a linear one with just one loop. I will have to struggle more with my brain :)
I'm wondering if there is better java collection to use than ArrayList? (in that current kata)
This comment has been hidden.
Next is please stop spoiling the kata and find the solution by yourself. I marked your post with a spoiler flag.
my math isn't that bad but the problem here is Im like 14 years old, does it have something to do with high school math or it's solvable for a year 8 student?
An issue is a bug in the kata. Please stop flooding the discourse page, you are supposed to find the solution by yourself, not being it given away.
apologize for the misunderstanding of the issue function, but first, im not asking for the answer, Im just saying is it solvable by a year 8 student secondly, I dont get it: how can you always track my feedback down and reply immediately?
I don't understand your question. All the comments published are visible by everyone (click
Homeat top of left panel).I have no idea of the maths school programs in your country. Though I think this is really hard for a 14 yo kid, though it can be feasible with a strong logical sense and good arithmetics notions. You also need to be somehow at ease with programming, I don't know how you are with it.
No high school math, just basic understanding of divisibility/modulo and a bit of logic. Don't give up, try a naive solution first (it won't work due to timeout), then sit down with pen and paper, and you'll get it eventually.
try to avoid using python :)
My solution passed, I don't know why.
Great kata anyway.
Tests 10 and 11 tell me that the arrays don't have the same size (I fulfill 10/12 tests), I can only see the stack of the exception, it doesn't show me what the test expects (which would be useful to guide me in the code correction) any suggestions? I'm working with Java
Just print the input : )
OP solved it, closing
After spending MUCH more time than I should've trying to optimize the code, I wonder why I didn't decide to just solve the equation in the first place, instead of using two loops with the same damn equation in the core. A great kata, actually
This comment has been hidden.
Think of this in that way:
For smaller n like 1000 you do 1000 * 1000 iterations (10 ^ 6) and it shouldnt make any problems,
But if n is 1 000 000 then you are doing 1 000 000 * 1 000 000 iterations (10 ^ 12).
Now compare amount of iterations done for n = 1000 and n = 1 000 000 (btw there are random tests for n as big as 1 000 000).
If you couldn't find the right way to do this kata you can look at the comments of others who give you direct approach you can use.
Same problem LMAO.
This comment has been hidden.
for me, the thing that helped me the most, was writing the equation out on a piece of paper.
Me too
This comment has been hidden.
I think it is too high. There are some cases with really large numbers, with 1 for loop is enough.
Yes, it is. You need an O(n) solution, not an O(n^2) one.
Ok, thank you.
Solved, I forgot to use the
reallocfunction.haha just when I thought I finally figured it out I noticed you had to give more than just one pair of numbers.
I really wanna cry rn.
nice kata btw
I spent almost an hour for this kata. Probably I'm kinda slower than other people. I can do it, you can too.
This kata is all about math. If you fucked up at math, go learn about sumation notation.
Don't ever think you can solve this with O(n^2). The test cases have big numbers. One for loop is enough.
How? I wanna cry.
Hahahaha, 1 hour for me would be a dream. Im spending already 4 and still nothing but a double loop that pass the tests, but doesnt pass the last one due to performance.
This comment has been hidden.
Good kata, I took advice from a comment below and did the math on paper, then the implementation was trivial.
Can you please give a hint? Probably I totaly forgot algebra, I don't understand how to solve it in the math way...
Awesome Kata! I was about to cry for help and give up when I got the right idea; it's actually pretty trivial. The only hints I will give: if your code times out, it's not the right way to solve this. And if you're really stuck, /// try solving it like you would solve a math problem, not a CS problem. ///
If you need help, feel free to comment under this post and I will try my best to help you figure it out. Took me about an hour and a half, but it was very satisfying in the end. You can do it too!
my math isn't that bad but the problem here is Im like 14 years old, does it have something to do with high school math or it's solvable for a year 8 student?
I like the fact that the trivial solution is failing for the big numbers due to the tests timing out, and you have to actually think about how to solve this one. Thanks for this kata!
This comment has been hidden.
This comment has been hidden.
Sorry there are no errors in the tests. BTW when you post an issue give the input, the expected result and your result. Furthermore look at the top of the page and see how many peole passed the kata in your language. If this number is high chances are that there is a flaw somewhere in your code. Cheers.
This comment has been hidden.
Issue with C expected pair format:
Error. Expected {{505, 811}{615, 666}{637, 643}{643, 637}{666, 615}{811, 505}} but got {{505, 811}{811, 505}{615, 666}{666, 615}{637, 643}{643, 637}}
Only "failing" this one test, which doesn't juxtapose the two like-pairs of each set together like apparently every other test case does. Only 182 of 12,347 C programmers finished this one, so I would call this an issue. Please adjust the expected order of the pairs.
Read the description. Your answer is not correct. Please read carefully this and don't raise issues lightly: https://docs.codewars.com/training/troubleshooting/
There should really be an example that highlights this.
For some reason I have complete Basic Tests which follows the "Test" Button. But when I entering the "Submit" button, Random Test is completed and Basic test is not. I can not figure out why
And it is't connected with the time - cod completes less than one sec
When you push submit you have 23 basic tests instead of 4.
Ok, Thanks!)
This comment has been hidden.
It is true -> -> Sum_of_array = (sum_of_array (1,26) - num_1 - num_2) == num_1 * num_2, but num_1 or num_2 > n (= 26) - so 175 > 26 - it is not correct. The condition of the task - num_1 or num_2 <= n (26)
Thanks! Good exercise! But I think is 6 or 7 kyu, but not 5 kyu. Because for O(n) you need know one rule from math and pair of condition for <O(n)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
could you give me a hint ? I use for loop, then time out...
im using 1 loop and also stuck
If your code reads through the whole list then it's probably not right. Think about the problem like a math equation
I have a mathematical equation that checks for x and y in one for loop, but still need to pass a loop to solve it...
I pass the test but I cannot pass the attempt. :(
The next morning I came up with a frustratingly simple solution that makes you wonder, man, are u stupid?
A lot of dust had to be blown off my school maths to get this to pass efficiently. Thanks for the challenge - boy I found this haaard!
Gorgeous kata! I thoght of it all day and can't sleep tonight unlit it's done
wow. one of the best challenges on this website. thank you
This comment has been hidden.
Before posting issues look at the top of the page: 211 people passed the TS kata (11833 in all languages). If there were errors somebody would have seen them before you... Please read the description once more. Not a kata issue.
C#: src/Solution.cs(3,16): error CS0246: The type or namespace name 'List<>' could not be found (are you missing a using directive or an assembly reference?)
The following should be added to the initial solution setup:
Done. Thanks!
This comment has been hidden.
COBOL translation.
Approved.
This comment has been hidden.
fixed tests work fine, but when trying to submit the solution it times out
Timing out is not a kata issue: your code is too slow.
Amazing kata! Well done to creator, I just don't know why is it 5kyu and not 4kyu.
Thanks! It's not the author who gives the kyu...
I pass all the tests, but when I submit my program I run into an error because it executes too long. How can I see the example where my program is having problems with, so I con reply it by myself and see what's wrong?
You can read this https://github.com/codewars/codewars.com/wiki/Troubleshooting-your-solution.
Thanks
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Wonderful puzzle, as a newb in programming I learnt plenty to finish this kata.
I saw your puzzle history. How are you able to solve relatively advanced puzzles, as a newb?
can more than one combination exist
It is in the description.
This comment has been hidden.
Not a kata suggestion ~~ a hint instead ^^
This comment has been hidden.
Sorry but I don't have enough time to resolve your issues; maybe you have it. Maintening kata is - at least in my case - almost a full time job! Moreover I didn't think about possible cheaters when I authored katas... BTW I would have not thought you were one:-)
Maybe you should have marked your post as "Spoiler", no? Have a good day!
Added a JS translation, now your solution should TLE on it. Dunno about the other languages, if the people will ask about the problem in the other language I'll try to add a corresponding translation
This comment has been hidden.
Please see above.
Fixed the Ruby issues in this translation; also JS' version is now updated to Node 14
This comment has been hidden.
Having the same issue, I don't understand the instruction. It says return '' if more than one possible pair of a,b values, yet the tests ask us to return two pairs of a,b values?
Edit: Honestly, just ignore that criteria and anything about the amount of a,b pairs, just make a solution which returns the a,b pairs quickly and you'll pass.
This comment has been hidden.
Timing out is not a kata issue; it is because your code is too slow.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Why does the test have an issue with the same result? I thought my code was wrong till I realized it is the same thing!
Expected: [[550320, 908566], [559756, 893250], [893250, 559756], [908566, 550320]], instead got: [[559756, 893250], [893250, 559756], [550320, 908566], [908566, 550320]]
Yeah. That's what I did to pass the test. Hadn't seen it in the instruction. My bad.
This comment has been hidden.
"with all (a, b) which are the possible removed numbers in the sequence 1 to n."
You are returning values that are larger than n. Therefore, according to the directions, they do NOT "work fine".
This comment has been hidden.
It's not an error but a simple warning that doesn't prevent you to pass. Nevertheless I changed "assertSimilar" to "assertDeepEquals". Unfortunately your code fails.
WOW, what a great Kata! I spent almost whole day to figure out the formula. It was worth it. Added to favourites!
I'm getting this tests error not sure maybe I'm wrong by looks like tests checking only one particular sequence:
Expected: [[550320, 908566], [559756, 893250], [893250, 559756], [908566, 550320]], instead got: [[559756, 893250], [893250, 559756], [550320, 908566], [908566, 550320]]Maybe the instructions have something to say about how that should be presented.
Yes, my fault. Thank you. I found the line with explanation that out should be sorted. There are so many words about friend etc. that I miss the impotant part :D
This comment has been hidden.
I love this kata! It literally rememberd me of the math tricks from high-school (like a = b <=> a+1-1 = b). Thank you!
I don't get it. How would you use that trick in this kata?
This comment has been hidden.
Did you thing of that part of the description:
Made it! Thanks a lot.
Code works except for the higher value (500003500006). It either times out or returns this: FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
Not a kata issue, that's a problem with your code and no test has an input value that high in javascript.
should work for higher number Log 500003500006
Copied and pasted this from the output after running the code. There is a test with that value.
The highest input value of those tests is
1000008. Are you logging them without doing anything else before, right?Your code probably uses recursion and it's overflowing the stack.
Yeah I was logging the sum by accident my bad. Not using a recursive function but rather a nested forEach loop which is likely the problem. Thanks.
Sometimes tests expect only (x, y) and sometimes (x, y) AND (y, x) which makes it impossible to pass. I use Python version.
Wrong. If it were the case, amongst the 3,064 people who passed the Python kata somebody would have already seen it, no? Please, before posting issues, always look at the top of the page to see how many passed the kata in your language:-)
How is it possible to return 2 values as a List of type long in C#? Like the form required [(a, b), ...]...or should I change it to a tuple of type long? like Tuple<long, long>[] removNb
This comment has been hidden.
What is your problem? You passed the kata... Not an issue.
The instructions are poorly written. (1,-5,47,n) fits the description of "a sequence of numbers from 1 to n." Sequence has a clear mathematical meaning and it is not as assumed here. It should be re-worded as something like "all integers from 1 to n" to fix this ambiguity.
This comment has been hidden.
Thank you very much.
you are right, sometimes just nedd to think more
thanks
Please check my reply in my previous issue report. I know you marked it as resolved but I don't think it's resolved yet. Thanks
Maybe there is some ambiguity in the description which have permitted to many to pass the kata. In life there are always ambiguities... To include "your" tests I should change the description and I think that nobody - even only a bit dishonest - changes the rules when the game is on. Moreover - can be seen as a bad excuse - I would have to modify the kata in its 32 languages and I don't have enough time for that:-) Sorry if I disappoint "your" point of view but mine is I can't change anything and, after all, it's my kata.
oh for sure my friend, it wasn't my intention to take over your kata. I'm not sure if I was rude or you're too sensible, in any case, sorry. I understand that takes a lot of work to change it and as it's right now it's a pretty good one, I am just picky programmer lol. I think that I backed "my" (lol) point of view with enough explanation to make it not-just "my" point of view, but it's not a big deal. Don't worry, I'm not dissapointed, it was a suggestion without serious expectations lol. Once again sorry for all the trouble and thank you for the kata.
This comment has been hidden.
Not everything you've said is true, check your assumptions.
.
Thanks, I see what I did wrong.
Fascinating kata! The performance requirements make this a deceivingly complex challenge. Somewhat astonisting how little code the performant solution requires. And I felt so proud of my cunning brute-force solution, LOL!
This comment has been hidden.
Interesting suggestion but I did not say explicitly in the description that "a" must be different from "b". To include these test cases, I should have made it clear somehow. Sorry.
I agree that you didn't speficy a!=b but if a=b there is going to be just one number to exclude from the secuence. A "solution" that return the pair (3,3) for N = 5 is wrong since (1+2+4+5 = 12) != (9 = 3*3). That's my point, altought I have to admit that my solution don't find pairs for a = b where 1+2+..+n - a = a*a. Don't be sorry, even the most popular solution don't check it. If your real intention was to allow a=b then please include a test for N = 3, 20, 119, 696, 4059, 23660, 137903, 803760 or 4684659, those have solutions for a=b. Thanks.
This comment has been hidden.
Print the input.
Well, thanks. Long day of work, didn't think this threw, mb.
But I can see that I passed the test with 26 but not the attempt with 26. I'm really confused here, spend so much time to get from 2 loops to 1 than now I can't see what is wrong.
Post what you have so far
Can't figure out how to reduce my 2 for loops to 1.... great kata though
neither lmao
This comment has been hidden.
This comment has been hidden.
My code works fine except I just don't understand why sometimes you need to return only one pair of integers when several others would work and sometimes you need to return more but not every single one of them. Could someone explain me this please?
I don't understand what you mean. You have to return all pairs that work and only these pairs. Moreover it seems you understood since you passed.
My bad I re-read the description and saw that it was pairs between 1 and n and not sum(range(1,n)). Thank you anyway !
This comment has been hidden.
This comment has been hidden.
.
This comment has been hidden.
Sorry, timing out is not a kata issue; your code is too slow. Moreover if you are asking for help post a question, not an issue.
This comment has been hidden.
Approved.
What a struggle at first! Thank you everyone for guiding me through it.
This comment has been hidden.
Nice kata, although it had me overthinking for a bit since I thought that it's going to be relatively difficult, but turns out that the implementation is not quite complicated.
Yes, I didn't think I was going to solve it, But I came up with an idea and didn't believe myself when it passed all tests.
This comment has been hidden.
Simple yet very funny and interesting Kata!
Thanks to the author!
Thanks!
This comment has been hidden.
Have you been using a walrus operator?
For now the kata is for Python 3.6
Awesome Kata, really had to twist my brain to come up with a solution that is fast enough with bigger numbers too.
Thanks!
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Already answered.
Just figured this one out, wow what a great kata. I know a bunch of you are having difficulties figuring out how to simplify your code, so just remember that you can have one for-loop and still be fine. Don't focus on making it completely in terms of n, just figure out how you can simplify the nested for-loop to a single for-loop. Great kata.
This comment has been hidden.
OK, there is a language abuse. I modified the description for C but if you have a better idea I'm ready to listen.
The update only removed the "should return an array of pairs" from the description, now we don't have any clue at all! What is still missing is what datatype SHOULD be returned, especially which parts should be allocated because they're going to be freed by the testcode (which is hidden from the user).
So what do you propose? Isn't the signature of the function sufficient since it gives the data type to be returned? In "Example Test Cases" it is said
Pair** arr will be freed.No, that's my point, it's not sufficient, and you cannot deduce it from the testcode visible to the user. An array is something very different from a pointer. A declaration Pair **arr does NOT declare an array. And even in C arrays can take multiple forms, which are not fully compatible.
Why don't you just describe what the data structure is, and which parts need to be allocated? That's all that's needed.
I don't understand what you exactly want me to write but if you tell me what I should write I certainly will modify the description for C (after all you seem to be the best at C). For me "Pair **arr" tells clearly what you have to allocate; the Pair structure is given; I don't say - as you seeem to think - that Pair **arr declares an array". Moreover lots of people passed the kata and as far I can see nobody complained about that until now.
I think the problem is in this: "For me "Pair **arr" tells clearly what you have to allocate", it shows you're not aware there are many other perfectly reasonable ways to declare and allocate a Pair**. Even if the description of the C data structure was ambiguous (which many Katas suffer from), one could try to deduce the structure from the test code. In this case it is not possible, because the returned value is neither directly used nor freed.
Having made some guesses about possible datastructures finally allowed me to see your implementation. The design of that data structure used a very poor and non-intuitive choice, which explains why it's not that obvious at all. A better choice would have been to just use 'Pair*p=malloc(x*sizeof(Pair))' for all Pairs once, and not allocate extra memory of each Pair separately at all. It would also simplify your code.
Here's my proposal for the C description: the function should return a pointer to an allocated array of Pair pointers, each one also allocated.
Thanks for the Kata!
I totally agree with nomennescio here. I think C API is horrible and unnecessarily complicated,
and tests themselves leak memory terribly. First of all, the type ofPair**does not suggest anything, because there are many things it could actually mean. Indeed, the "allocated array ofPair*" is one of such tings, but there are other legit possibilities. Other thing is that it's not even necessary. Why each and every pair has to be allocated separately?Why reference solution allocates each and every pair but tests do not free it later?Why just not return aPair*, and have solution to malloc somePair* result = malloc(sizeofPair) * some_count);? Just allocate one big block of memory for all pairs (growing if necessary) and put everything there. mallocing each and every pair separately is terrible overkill,and it's handled incorrectly by tests (because individual pairs are not freed).The fact that return type is
Pair**just raises doubts, because it raises the question: how shouldPair*pointers inside of it be produced? Should they be malloced? If so, will they be freed? Many questions, no answers, a lot of guessing.If it were up to me, I would change the function signature to return
Pair*, specify reqs in description and/or solution stub and do not worry about existing solutions, just invalidate them.EDIT: okay, after reading the code I can see that individual pairs are freed, in Preloaded snippet, by a string conversion function. So as much as such approach is... interesting, I was wrong about the leaks, sorry for that. The matter of individually allocated pairs still stays though.
@nomennescio: thanks for your proposition, adopted and description modified. For "'Pairp=malloc(xsizeof(Pair))' for all Pairs once", I thought of that but not knowing
xbeforehand I choosed another way i.e. reallocating as needed in a not efficient manner. @hobovsky: "horrible", "unnecessarily complicated", "terrible overkill", what a litany of words:-) I thought you usually were less sharp... I don't like to “invalidate” solutions because I think it's kind of disrespectful for the work of people who have been unintentionally misdirected.Now if I see a benchmark where C is slower than Java or something like that, I'll know how they do it.
@g964 "but not knowing x beforehand I choosed another way i.e. reallocating as needed in a not efficient manner"
That was not my point. Reallocating is fine. My point is that you don't need an array of Pair pointers, just an array of Pairs is better, i.e.
Pair *p=0; int n=0; .... p=realloc (p,++n*sizeof(Pair)) .... p[n-1]=(Pair){a,b}; .... return p;(B.t.w. For all people who have learned C from the still popular "The C Programming Language" be aware that the C dialect in there is more than 30 years old, and terribly outdated)
But even then, you can realloc an array of
Pair. The fact that reallocation is done for every added entry (as you noted it's not efficient, but it's not the point of this discussion) does not mean that entries should be pointers. In this case here, reallocating an array ofPair*is not better than reallocating an array ofPair.Yeah you are right, I think I missed my chill pill today and I got triggered really hard ;) Please don't take it personally, because my rant was not directed personally towards you, but rather the fact that C kata on Codewars are usually authored without much thought put into requirements on memory management. C is very different than other languages in this aspect, and things need to be designed and described with more details. But authors seem to know only one technique: MALLOC EVERYTHING, DESCRIBE NOTHING. Once I've even seen a kata which required returning a a single malloced
Point. Whenever I come accross a C kata, I never know what memory management approach I should take, because it's never specified, and the one which is in my opinion most suitable does not work. Newbies come around such kata, and they need to do a lot of head wrapping which would not be necessary if things were explained appropriately.You updated the description, and that's good, now people know what to do. Required approach might still be not perfect, but now at least requirements are clear.
@hobovsky check my entry, LOL.
As for your "Whenever I come accross a C kata, I never know what memory management approach I should take, because it's never specified, and the one which is in my opinion most suitable does not work.", that's very recognizable. Even Linus recognized that C programming requires tight memory management, a skill which is usually lacking in the less experienced, typically by using languages that more or less hide memory management.
"Quite frankly, even if the choice of C were to do nothing but keep the C++ programmers out, that in itself would be a huge reason to use C." (On why he thinks C++ is a horrible language and no suitable choice for Git). I tend to agree.
In general (I haven't read this thread closely so I don't have any opinion about this specific issue), I don't think there's anything "disrespectful" about solutions being invalidated. Invalidating existing solutions shouldn't prevent improvements, especially when the number isn't that high. There will be more users attempting in the future and it's better to improve their experience.
It was fun to find out, inner loop is simply replaceable by an equation. Algebra is needed to solve the "Execution Timed Out (12000 ms)" Great exercise
This comment has been hidden.
I guess both.
As far as I see, C++ version has 100 random tests with n going up to ~320_000, and a couple of even bigger fixed tests. My solution is O(n) and it passes, but you mention two loops, what might suggest your approach is O(n^2), so it could be too slow.
I presume this must be the sequence {1,2,3,4,5,6....n} but I don't see anything in the description to confirm this?
Why do you need anything else to confirm this? Doesnt the thing you quote already confirm that?
Here are three other sequences from 1 to n (where n>0): {1, 2.5, 4, 5.5, 7, ...n} (a_n = 1.5n - 0.5) {1, 3, 5, 7, 9, ...n} (a_n = 2n-1) {1, -2, 3, -4, 5, -6, ...n} (a_n = n*(-1)^(n+1))
I agree. It should say n > 1 AND integer in my opinion
Python version should use snake_case.
.
Thanks. Not sure why there is no e in "remov" though!
par "omnipotentia":-)
This comment has been hidden.
This comment has been hidden.
You will need an O(n) solution rather than O(n^2) in order for the code to meet the 12 second deadline for the large values of n in the 'Attempt' test suite. Also, 'a' and 'b should always be distinct values, so I think you might have an uncaught bug right now too.
This comment has been hidden.
Avoid nested loops.
Hi I have a Problem in C++. So i get the correct Values, but if i push them into my vector<vector> I get the error message "wrong return type". If I push some random numbers into the vecotr everything works. Even if I push, like in the first test, 15,21 into the first vector and then 15,21 into the second one everything works, but if i push 21,15 into the second one it magically wont work anymore (at least it seems to me). Has anyone experienced the same problem?
I just solved C++ version and found no problems with it. I cannot really get what oyur problem is from your description, so I think you'd have to show some code so we could take a look. One thing to beware though: note that kata works with
long longitems, so if you use int literals in your code, be sure they are not narrowed tointbecause then you can sometimes get type errors on compilation.Thanks for your answer, I solved it in another way and still have no idea why it didnt work the other way around.
Just FYI on R, it requires the list elements to be sorted on the first number (a). If you submit the same list just ordered on b, you will get errors.
The description says:
and the tests make it clear.
that is very correct. My bad.
This comment has been hidden.
This comment has been hidden.
Its probably because your code is not optimised enough.
The 3 pre-set tests each use very small numbers for n however the actual tests that get run when you submit use much larger numbers for n.
The issue then is that if your code takes too long for the cdewars server it will time out.
Test your code in a local environment and see how long it takes, if it takes longer than codewars allows before timing out then you will have to change your approach to one that takes les time.
Yeah, you are totally right. I've found a problem with big n.
but in the and this kata is more about pure mathematic, and less about algorithms. You can be super-bruse-lee-algorithm master, but if tou don't know math solution of this - all your attempts will fail.
Made it! I really learned a LOT from this Kata and it directly pushes me to turn to gcc in linux from VS! Thank you Sensei!
Some languages do not have random tests, e.g Haskell.
Hi all another question: as per the returning type of removeNb I have a Pair** type pointer as the return value, but from the instruction and the debugging error I got, the return value shall be a 2-D array as {{15, 21}{21, 15}}. Apparently I got {} as the submitted value. Anybody can give a hint on that? How it is possible to return {{15, 21}{21, 15}} as a Pair** type?
You have to return a
Pair**type and the functionchar* array2StringData(Pair** arr, int sz);transforms your return in achar*to test that return.OK thanks! It's just that with my IDE I can always get my output as Pair** but here with gcc or my submitted array is {} or I get double free or corruption error with so many trials. I don't know what kind of hints I can get for my problem.
Hello all! could anybody tell me what the hack the parameter length means?
Didn't you see the comment in the initial solution?
yes right I missed that, thank you sensei!
Really challenging kata for me, had me so frustrated at times. Anyone who's stuck, the other comments here will guide you in the right direction.
This comment has been hidden.
Asking for help is not an issue, sorry.
Try to write in down and move variable around the equation. I hope this will help.
This comment has been hidden.
The problem you are facing is your nested loops. For small numbers like 100 they will work fine but if you get a number like 100000 then it will have to loop through 100000 number 100000 times which is doable but takes a very long time.
If it takes longer than the codewars server allows for execution time then it will timeout.
You need to find another method of running a check that uses less or no nested loops (the optimisation lies in the algebra before the code).
This comment has been hidden.
We can't see your code, so please post it with a spoiler flag.
This comment has been hidden.
This comment has been hidden.
Hi, I have I problem testing my code in C. Maybe I did something wrong but the function
array2Stringfunction gets an INVALID MEMORY ACCESS while testing. The weird thing is that if I comment out the call toarray2Stringand print the array... it works without problem. Could you please help me?Not an issue but a question. Something has to be wrong in your code since 93 guys passed the C kata. I tried a few solutions and all worked fine.
Ook, thanks for the reply. Could you can give me some hints on how is implemented the array2String function to understand what's wrong. I tried to implement one on my own and it worked. If it's possible. thank you .
I don't have much time but I think you have a problem when allocating a new pair.
I want to thank everyone who suggested the use of pen and paper, it becomes very simple once you get the algebra behind the problem.
7AM here, and I am finally done with this one! Congratulations on the creator for keeping me home on a Friday night...
im always getting time out...
One of the best 5Kyu's I have solved... Use pen and paper people...it will just come to you!
Thanks again!
thanks for the tip to remind me to use my brain haha
Was at same position :)
it didn't just come to me but thx i guess
Awesome kata. Not all the solutions are made of code, this one proves it. Try to play with algebra, then you will easily solve it in a few minutes.
Big thanks to authors!
Thanks!
thanks! totally disregarded fundamental math and tried smash my way through the solution.
This comment has been hidden.
Strongly suggest letting users know that time constraints will be a concern and to prioritize timing, was frustrating taking a more "coder" approach only to realize after reading comments that i should use algebra. Otherwise, great kata!
I can't resolve the kata on PHP becouse take timeout during attept tests.
Sorry, not an issue. If you timeout it is because your code is too slow.
This comment has been hidden.
Your code is too slow. Try to solve it with only one for loop - O(n).
This comment has been hidden.
Using Vec<(i32, i32)> as output in Rust requires everybody to sort their solutions the way the author wants. Using a HashSet<(i32, i32)> would be more fitting. Also, since the numbers are strictly positive, u32 should be used instead of i32.
The feeling I got after thinking that I suck at math for so many years and finally solving this kata...
This comment has been hidden.
This comment has been hidden.
Thank you, i found a way that gives me b by using sum and a and O(n) works perfectly. Thanks
This comment has been hidden.
This comment has been hidden.
This Kata is a nice little algebra problem, not really a coding challenge per se.
However -- I think it's silly that the test examples contain such small numbers and the description makes no mention of constraints on algorithmic efficiency.
It's like the designer wants to bait you into choosing a brute force method and then GOTCHA! the actual test suite contains very large numbers. I'm not sure why this is. For many programmers, choosing a brute force method will be quicker and more natural than doing a little algebra to find a method with O(n). It's clear from the comments here that this is confusing to a lot of users.
TLDR - Kata would be significantly improved by providing a clue about its true constraints.
This comment has been hidden.
Sorry, it's not an issue of the kata. If you think it's a server problem report it as a bug at CW. Look at the top of the page and see how many guys passed the kata. Cheers.
It looks like I need to brush up on my math. I tried the easiest way - loop within loop which is going to take forever with bigger numbers hence the server's refusal to execute the code.
This comment has been hidden.
This comment has been hidden.
I think you should read the description again. Cheers.
Silly me.
a,b <= n, not sum(n)
Thanks for the quick reply. :)
This comment has been hidden.
you forgot to paste the imports.
Thank!
I thought that I could write my code only inside the method.
I received a new error message: Execution Timed Out (16000 ms)
Apparently, my algorithm is bad.
yep, too slow. ;)
This comment has been hidden.
Not at all... The tests are almost the same in all languages and note that 4791 guys passed the kata.
Not a problem. You can add tests with bigger numbers (maybe trying first on a sheet of paper and a bit of thinking).
how is this an answer? it is irrelevant whether tests are same or not across languages. and it is irrelevant how many people passed.
there is an issue with description which doesnt mention that you cant solve this kata by brute force which is what anyone would try first.
solving it without brute force requires absolutely different approach, but somewhy everyone has to figure this out, why? or you wanna say someone solved this with brute force?
You are terribly wrong here accusing the author of this kata in some sort of deceit. g964 spent time creating this interesting kata. It's not kyu 8 kata, it's kyu 5 and all kata of this level are expected to be solved by a more advanced algorithm than a brute force one. If you are expecting naive algorithms, maybe it's not a bad idea to try kata kyu 7-8.
in what exactly am i terribly wrong?
it is irrelevant how much time he spent, it is even irrelevant who did this kata.
"It's not kyu 8 kata, it's kyu 5 and all kata of this level are expected to be solved by a more advanced algorithm than a brute force one." where is this written? and why is this a bad idea to write that again in description? you can obviusly see how many people try to solve it with bruteforce at first, because that is the easiest solution.
also what you think about g964 answer
"Not at all..."
is it possible to solve this with bruteforce? based on your answer i think it is not possible.
well if it is impossible then it is a condition that is implicit(if there is somewhere written that all 5 kyu cant be solved with bruteforce in any language). why is this a problem to make this condition explicit?
I wonder if something like
cytoolzwould help brute forceplaying with list in this case isn't good idea ? my solution is extremly slow O(n*2) maybe any hint :)?
This comment has been hidden.
This comment has been hidden.
OP solved it, closing
This comment has been hidden.
Maybe my eyes are tricking me, but those look like similar arrays to me.
will be sorted in increasing order of the "a".
Yep. Missed something obvious. Thanks.
Wow, that took me a while. It has been a really long time since I did much algerbra. Pretty cool!
This comment has been hidden.
Your solution is O(N^2). There exists a formula that can help you solve the problem with just O(N) time complexity. (1-time iteration)
Wow... This is really stupid.
removNb(26) should return [(15, 21), (21, 15)]Why should it return same numbers twice? This is kata design flaw. And it got translated to shitton of languages. Awful.How nice:-)
It definitely wasn't nice but he certainly has a point. WHen I first saw it, I right away jumped to the comments. I refuse to solve it if the solution involves duplicating every single pair. It's not mathematically correct and quite inefficient.
This comment has been hidden.
You can print out the arguments, it is very big.
I came back to this kata with fresh eyes now. The way I was doing it was messed up. Figured it out now. :)
This comment has been hidden.
This comment has been hidden.
Yes, part of it is very well known. As a hint, any time on CodeWars where it talks about sums of lists, it is almost always the case you often don't need to sum it but there is just some formula to calculate it directly.
There are a bunch of katas related to the sums of a list which are missing a number, have a number duplicated, etc. . They are all very close related.
This comment has been hidden.
This comment has been hidden.
No matter how I modify it, it prompts timeout.
hi. test10 gave error "Arrays not the same length" Incoming value: 1000003 Result pairs are: [[550320, 908566], [908566, 550320]] and this answer is correct, but the test doesn't pass Why?:(
You could have seen at the top of the page that more than 600 guys passed the Java kata so if there were errors somebody would already have seen them. In that case don't post an issue... Your answer is incomplete hence you don't pass the test.
this is also an answer: [559756, 893250]
Does this kata has a problem? I keep getting the "execution time out" error even after optimizing the code endlessly.
No problem: you could have seen at the top of the page that 966 guys passed the Python kata (BTW don't forget to give the language you used). Moreover it's a question, not an issue.
Well,your katas haven't been the best. instructions always misleading.
I can get my code to solve the problem, but it times out with the higher values.
I can use a simplified code to find only one solution, but that doesn't satisfy the conditions either.
A lot of the time this happens, there is some math trick to solving the problem vs some code optomization.
This comment has been hidden.
...That's not an issue.
If your code fails the tests but you don't know why, you should post your code formatted and marked as spoilers, and post it as a question. Issues are not for inquiries about your code.
I am currently not passing even the simple sample test where n = 26, which should return [15, 21] and [21, 15]. My error is that essentially the arrays are flipped, returning [21, 15] and [15, 21], so the arrays differ at each element. When running my own IDE and test cases, this is not the case. I can see clearly that I return [15, 21] followed by [21, 15]. I do not understand why this is happening on the CW site. Anyone else same issue?
From reading the other comments/questions, I understand that I may run into some complexity issues later, but its frustrating that I cannot even pass these sample tests on CW.
Maybe your code relies on some undefined ordering behaviour? e.g You're turning a set into a list, but you forgot to order the result afterwards.
A nice little problem - easy to time-out. Why not use "a" in place of "i" in your solution? :o) I think your description with "chooses two numbers, a and b" is quite clear, a and b are not the same number, jcolicchio. But what happened to n being "relatively small"?
Seriously. The description makes it seem like the algorithmic complexity isn't a factor. I would have approached this problem completely differently if I'd known the "relatively small" n would timeout. A bit frustrating to be honest, especially considering how many comments are pointing this out.
The instructions seem ambiguous regarding whether or not you can select the same value for a and b. There are three interpretations I can come up with:
(Remove a once) The sum of 1..n - a must be equal to aa In this case, (14, 14) is a solution for n=20, since 210 - 14 = 1414
(Remove a twice) The sum of 1..n - a - a must be equal to aa In this case, (10, 10) is a solution for n=15, since 120 - 10 - 10 = 1010
a and b must be distinct In this case, neither (10, 10) for n=15 nor (14, 14) for n=20 should be accepted as solutions
Judging by the wording of the problem, I would assume interpretation 1, since the value a only shows up in 1..n once, we can only remove it from the series once, and (1..a-1) + (a+1..n) should be our target sum
However, occasionally {a, a} shows up as a solution in the random trials, and the solution grader behaves consistently with interpretation 2. That is, the sum of 1..n - a - a must be equal to a*a
I understand how this can be a valid interpretation mathematically, but I think the word problem framing this question leads to some ambiguity
i'm escalating this as an issue, as this is a fundamental ambiguity with the problem statement.
This comment has been hidden.
can't be changed
argh i pass every test but apparently my code doesnt execute quick enough :(
O(n) enforcement made this fun :D
This comment has been hidden.
This comment has been hidden.
Hi. Im not sure if it's just some dumb problem on my side, but whenever I try to run the tests or attempt(Java), it throws this compilation error(even if there's just return null in the method):
/home/codewarrior/src/main/java/RemovedNumbers.java:3: error: cannot find symbol public static List<long[]> removNb(long n) { ^ symbol: class List location: class RemovedNumbers
Thanks.
It won't let me write it, but List has type of elements long[] and the little arrow is pointing at "L" of the word List.
null is not a List. Check you're importing the right libraries too.
My bad, I'm new to Java, I thought return nil meant that, thank you.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
one more idea write equlation
(C) It's seems like a heap overflow, is this normal or am I missing something? (I only allocated the Pair to return)
The output is an array of pointers to pair:
Pair **. Here you allocate only one pointer to a pair:so your solution crashes, because after the first pair you are writing out of bounds.
This comment has been hidden.
Your code is timing out because you are computing
sumof the long list twice in the for-loop. Instead, you can store the value before-hand or even better try to come up with an O(N) complexity-based algorithm.