We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Cut the sticks
Cut the sticks
+ 1 comment There's no need to actually do the "cut" part, and it can be done in just two passes. The insight here is that number of sticks after all the chops in one round is a number of sticks with the higher length.
sticks-length sticks-cut 5 4 4 2 2 8 6 3 2 2 _ _ 6 4 1 _ _ _ _ 4 2 _ _ _ _ _ 3 1 _ _ _ _ _ _ DONE
+ 0 comments My humble Python solution:
def cutTheSticks(arr): result = [] while arr: result.append(str(len(arr))) short = min(arr) arr = map(lambda x: x - short, arr) #Substruct the minimal value arr = list(filter(lambda x: x > 0, arr)) return result
+ 0 comments without using while. It just uses sort and 1 loop to reach to answer
vector<int> cutTheSticks(vector<int> arr) { sort(arr.begin(), arr.end()); vector<int> result; result.push_back(arr.size()); int smallest = arr[0]; for(int i=0; i < arr.size(); i++) { int elem = arr[i] - smallest; if(elem > 0) { result.push_back(arr.size()-i); smallest += elem; } } return result; }
+ 0 comments C#
public static List<int> cutTheSticks(List<int> arr) { List<int> stickCut = new List<int>(); stickCut.Add(arr.Count); arr.Sort(); while (arr.Count > 0) { int min = arr[0]; for (int i = 0; i < arr.Count; i++) { arr[i] = arr[i] - min; } arr.RemoveAll(x => x == 0); stickCut.Add(arr.Count); } stickCut.RemoveAt(stickCut.Count - 1); return stickCut; }
+ 0 comments C# Solution:
class Result { public static List<int> cutTheSticks(List<int> arr) { List<int> result = new List<int>(); result.Add(arr.Count); while(arr.Count > 0) { int min = arr.Min(); arr = arr.Select(num => num - min).ToList(); arr.RemoveAll(num => num <= 0); if(arr.Count > 0) result.Add(arr.Count); } return result; } }
Load more conversations
Sort 1857 Discussions, By:
Please Login in order to post a comment