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.
// return negative number if not found
// otherwise pivot is returned.
// caller can print 5 x pivot + 3 x (n-pivot)
int getPivot(int n) {
while(n > 0) {
if(n%3 == 0)
break;
else
n -= 5;
}
return n;
}
While the time spent to compute the number of threes and fives to print is well reduced, you still have to print N digits, so technically the complexity still is O(n).
you see O(1) means that its constant time but the constant(Eg:O(1000000)=O(1)) however big is rewritten as O(1) for the sake of simplicity. well maybe what he is trying to say is that maybe his constant is smaller(i am not sure if it is). i i am just trying to tell you that Alg1 maybe faster than Alg2 even though both of them hve the complexity of O(1).
The loop in this iterative approach will run at most 2 times, which technically makes this solution O(1) as well. However, it should be obvious that the direct formula will require fewer machine instructions. By counting just the math operations (so ignoring jumps, which inflate the cost even more), it breaks down like this (please comment if I made a mistake!):
Direct (2 x N % 3):
+ 1 Multiply
+ 1 Mod
= 2 Constantly
Iterative:
Best Case (N is divisible by 3):
+ 1 Comparison ( while(n > 0) )
+ 2 Comparison and Mod ( if(n%3 == 0) )
= 3
Worse Case (N % 3 == 1), full loop runs twice:
+ 3 Comparison ( while(n>0) )
+ 6(3x2) Comparison and Mod ( if(n%3 == 0) )
+ 2(2x1) Subtraction ( n -= 5 )
= 11
And we might as well do the 3rd case (loop runs once):
+ 2 Comparison ( while(n>0) )
+ 4(2x2) Comparison and Mod ( if(n%3 == 0) )
+ 1 Subtraction ( n -= 5 )
= 7
Since each case is equally likely, we calculate that the average cost is (3+7+11)/3 = 7 instructions.
So although both solutions are O(1), we can correctly conclude that the iterative approach is ~3 times more expensive. If we counted jumps and assignments, it's more like ~4 times. This is a significant difference.
I might be wrong :). But I can still get a result even with N=1000. What is the correct answer for N=1000? Also I don't understand why you need to check (pivot%3 != 0) while it is checked in getPivot() function.
My answer to N = 1000 is
5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555553333333333
yeah finding the pivot is important. My solution is similar. I aimed to remove the expensive operation "modulo", here's my solution.
#Python solution without modulo
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
x = (int(n / 3)) * 3
y = 0
while True:
y = n - x
if ((int(y / 5)) * 5 != y):
if (x == 0):
print("-1")
break
x = (int((x - 1) / 3)) * 3
else:
print (int(x) * "5" + int(y) * "3")
break
Sherlock and The Beast
You are viewing a single comment's thread. Return to all comments →
This function works quicker than of editorial.
So you can do this:
am i missing somethign here? The editorial solution is O(1) how is this faster?
Missed the new O(1) solution was added while the complexity on the right side was still O(N)
While the time spent to compute the number of threes and fives to print is well reduced, you still have to print N digits, so technically the complexity still is O(n).
you see O(1) means that its constant time but the constant(Eg:O(1000000)=O(1)) however big is rewritten as O(1) for the sake of simplicity. well maybe what he is trying to say is that maybe his constant is smaller(i am not sure if it is). i i am just trying to tell you that Alg1 maybe faster than Alg2 even though both of them hve the complexity of O(1).
The loop in this iterative approach will run at most 2 times, which technically makes this solution O(1) as well. However, it should be obvious that the direct formula will require fewer machine instructions. By counting just the math operations (so ignoring jumps, which inflate the cost even more), it breaks down like this (please comment if I made a mistake!):
Iterative:
And we might as well do the 3rd case (loop runs once):
Since each case is equally likely, we calculate that the average cost is (3+7+11)/3 = 7 instructions.
So although both solutions are O(1), we can correctly conclude that the iterative approach is ~3 times more expensive. If we counted jumps and assignments, it's more like ~4 times. This is a significant difference.
It fails in some cases for ex: when N=1000 :P. PS: adding if(pivot%3!=0) pivot=getPivot(pivot); before checking for if(pivot<0) solves the prolem.
I might be wrong :). But I can still get a result even with N=1000. What is the correct answer for N=1000? Also I don't understand why you need to check (pivot%3 != 0) while it is checked in getPivot() function.
My answer to N = 1000 is 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555553333333333
you see there are 10 number 3 in this string.
yeah finding the pivot is important. My solution is similar. I aimed to remove the expensive operation "modulo", here's my solution.
why are you putting a solution in the discussion?
import sys can u telll me what is error in my code
t = int(raw_input())
test = 0
for a0 in xrange(t):
Can someone please explain the code for me especially the "getPivot" function? I don't get it...