sreejith_menon My simple solution of the order
log n, it passed all test cases. My logic was that there was a pattern between the actual time and the time displayed on the stop watch. Am I missing something here? Many of the solutions here seem to take complex approaches.rem = 3 while t > rem: t = t-rem rem *= 2 print(rem-t+1)
sahil_chanchad Can you explain your code
s92014721 Basically you find where the closest 1 is and subtract out the difference from the actual t.
laymann You are awesome!
sreejith_menon Thank you! :)
sachin_hg Can this be any simpler !!! :)
BlackVS Yes. No loops. Only few math ops. https://www.hackerrank.com/challenges/strange-code/submissions/code/36756057
Ridhuvarshan Cool. I forgot math, so i can't do stuff like this :p
atreidex same as my solution. but power and log functions also has loops.
malli9603112487 what is that math formula .i figured that in every cycle second element be same .but unable to construct formulae
josef_klotzner assume a range number (rn) of the counter where it starts counting back
for t =1 rn = 0 ...
for t= 4 rn = 1 ...
for t= 10 rn = 2if we are able to calculate this rn we know in which range t is in and the rest ist just work out differences. let us define t start limits (sl) first (1, 4, 10, 22, 46,..): if you do the following, you see that the row is directly dependent of powers of 2: subtract 1 from the row:
1, 4, 10, 22, 46 -> 0, 3, 9, 21, 45
divide by 3 (the whole counter ranges are divisible by 3)
0, 1, 3, 7, 15, ..
can you see already? it is just 1 behind the row of powers of 2:
1, 2, 4, 8, 16
now let us pack this knowledge into formula: (** = ^)
sl = 3 * 2 ^ rn - 2
f.e. (see above) rn = 2 -> sl (a special t) should be 10 and ...
3 * 2 ^ 2 - 2 = 10 .... great!
now, to get the "range" first, we need to "reverse" (i am sorry - no native english speaker - deutsch: "Umkehrfunktion" the power function, which is log with base 2:
sl + 2 = 3 * 2 ^ rn =>
2 ^ rn = (sl + 2) / 3 =>
rn = log2 ((sl + 2) / 3).... and make this an integer:
rn = int (log2 ((sl + 2) / 3))
Huh! To make it might be not soooo easy, but trying to explain it even more. Hope this helps figuring out to finish.
mike_buttery Start with the base values (using python here) and given
tt = 1, 4, 10, 22... v = 3, 6, 12, 24...=>t = 3 * 2**n - 2We can solve for
nn = math.log2((t + 2) / 3)We can get the base value
Bvof alltby flooringnBv = 3 * 2**(n//1)Next look at the sequence
t = 10, 11, 12, 13... v = 12, 11, 10, 9...vis twice the base value of each sequence minustminus 2v = 2 * Bv - t - 2So we can solve with
int(6 * 2**(math.log2((t + 2) / 3) // 1) - t - 2)
borisov_andrew_a Only math and less math https://www.hackerrank.com/challenges/strange-code/submissions/code/80406038
x_curveball_x test case 1 is not satisfied
groote how to see your code as soon as i click on this link new page open then just got dissappered
x_curveball_x test case 1 is not satisfied
debasis_jana_iit constant time .. long cycle = Double.valueOf(Math.ceil(Math.log((new Double(t) + 3) / 3) / Math.log(2))).longValue(); double p = Math.pow(2, cycle - 1); long start = 3 * new Double(p).longValue(); long rem = t - (3 * (new Double(p).longValue() - 1)); return start - (rem - 1);
rishabhrrk Can you explain. This is very nice.
debasis_jana_iit 3, 6, 9, 12 .... geometric series. so sum = a(r^n - 1)/(r-1) with a= 3 r = 2 and sum = t (given time). from this equation i get 2^n = (t + 3)/3 and i get n = log2 (t+3/3) and n is cycle. in which cycle t belongs. now start is my current cycle start number. now how long i will decrease my start. that's i get from rem variable which is t - previous cycle last time.
it's simply a concept of geometric sereis
aquibbaig Correction: 3, 6, 12*
amdokamal This is Geometric progression of Power of Two, i.e. 3*1 +3* 2 + 3*4 + 3*8 + ⋯ . Logarithm is required to find N-th term (or the nearest term) of Geometric progression. See another example.
Abe10 Exactly what Chandler would've said!
hemendrav4 You are awesome! Thank you! :)
ppprockrahul It's work but why u use -t+1 as in every case at last t will be 1
learner_codes splendid :)
LouManChuu Wow. I knew I was overcomplicating things. You did in 5 lines what took me about 50. Very elegant. Beautiful.
mboros I came up with the same solution in C++ and I was getting time outs on several test cases
MrAsimov same solution in C.it passed all test cases.
Damster In C++,
while(t>lower+upper-1) // lower = 1 , upper = 3 lower+=upper, upper*=2; cout<<upper-(t-lower);
quachtridat Same here
#include <iostream> using namespace std; int main() { unsigned long long val = 3; unsigned long long idx = 1; unsigned long long t; cin >> t; while (t-idx >= val) { idx += val; val *= 2; } cout << val - (t - idx); return 0; }
shashichalla mine had the same approach
Damster [deleted]
aleksei_maide had timeouts in C++ until changed to long instead of int... i guess the while statement didnt end with int's range...
PortgasAce [deleted]PortgasAce Does it pass all test cases ? I doubt
marigabibenitez [deleted]sreejith_menon It does. You can try it too.
krishnna really very nice logic
mananrajn Simply amazing man...and here i was stuck trying to solve it in such a complex way...Kudos !
zehranur this is awesome!!
vvbhandare Getting timeout for TC - 4, 5, 6, 8
kb2232 It is not Big-O (log n). It will not pass all test case
sreejith_menon It passes all the test cases and for each iteration, n is cut down in half. Hence a
logcomplexity.
shubshubham256 stupid man!!!! its giving wrong answer.
kb2232 try this: it might not work completely: O(1) int main() { long int t; int x, ans; cin>>t; x = 3*pow(2,floor(log2((t+2)/3))); ans = 2*(x-1) - t; cout<
sreejith_menon Thank you for your comment. :) Why the rage sir?
I passed all the test cases.
x_bcn23 [deleted]bgreenfield my solution was identical save in another progamming language.
Forbidden_Devil That is amazing... I always wish to come up with a solution like this..
bharatherukulla awesome
bgreenfield my solution is the same. you didnt miss anything people with more complex solutions are using a hammer and looking at it like a nail. thus missing the simpler solution.
palanisamy_mada1 what about t=10
piyushjaisingkar You are really good. #Respect.
soumyadas047 Great Solution
Amsaveni You are great!
CCWorldTraveler I did the exact same thing in python. Glad someone else was on the same wavelength.
It did take me a second try since initially, I did a serial subtraction of t, but that was orders slower and forced me to think about the number pattern.
A bit easy for a difficulty of 30, but I'm not complaining!
kshivam213 Awesome :)
wryan42675 Your solution is good, works in many languages, but int Java 7 it times out for some test cases, so in that language a faster solution is needed. Seems to me that the timeout period may have been too short because your solution is O(log(n)).
tomek_bawej Someone's hint about inadvertently using an integer in the main loop turned out to work for me too against the time-out. Anyway, by the time I noticed that I had a working code for performing binary search for exponents rather than looping up. Overkill for sure, but a fun exercise all in all.
fernando_luz I made the same approach.
:-)
ajayknit2011 static long strangeCounter(long t) { /* * Write your code here. */ // System.out.println("value of t"+t); // long rem=t%3; // long count=t/3; long stable=0; long temp=3; for(long i=1;i<=t;i=i+temp){ if(i==1){ continue; } else{ temp=temp*2; }
stable=i; } stable=t-stable; if(t==1){ temp=3; } else{ temp=temp-stable; } return temp; }dixitanmol97 SIMPLY AWESOME
Tsvetoslav88 The solution is working but I can't catch the logic for the solution
bdchambers79 That was my first solution, but it times out in C#
VikashOP That is awesome !!!
nadiyakhurshid98 some testcases went timed out !
Tandilashvili This is much more efficient way:
function strangeCounter($t) { $scnt = 3; while ($t+2 >= $scnt) $scnt *= 2; $scnt /= 2; return $scnt-($t - $scnt+2); }
Rishabh510 never thought of doing it this way. My approach was a lot longer;
NoneCares WOW
imskv420 In Python :
t=int(input()) b=3 summ=4 if t>3: while summ<=t: a=summ b=b*2 summ=a+b print(summ-t) else: print(4-t)
advaithsurya Genius level intellect ! Coming to a conclusion to there is a pattern is fine. But to execute it with such ease, nice
liuyuhao717 Thanks You, I got this solution. I didn't think deep enough
static long strangeCounter(long t) { int i = 1; int rate = 3; while (i + rate <= t) { i = i + rate; rate = rate * 2; } return rate - t + i; }After Improve my code from your code
static long strangeCounter(long t) { int rate = 3; while (t > rate) { t = t - rate; rate = rate * 2; } return rate - t + 1; }I still cannot pass the time cases
aditisingh1400 Amazing!
sarathy_v_krish1 C++ solution :
#include<iostream> using namespace std; int main() { long bound=3, t; cin >> t; while(t>bound) { t-=bound; bound*=2; } cout << (bound-t+1); }
meghnavarma0 your approach to solving this problem is very simple and catchy...each time the loop executes, the value of t decreases...leading to reverse pattern of respective times in stop watch and in actual as soon as the loop ends...
camkoolkarni your logic is so awesome
Iqra77777saleem can you explain how this solution is in log n
pawansinghla How can you think this approch.
mogonen genius...
kumarsurajsingh1 Its very optimize. good
wooddoo This is actually a math problem. Assume t is in the cycle with size 3*2^k, then k = floor(log2(t/3+1)). So, the problem is O(1).
Gerard0 It took me a lot of time to figure out how to calculate the first value of the colum. Just that it should be log2((t-1)/3 + 1).
This was really helpful. Thanks!
avasansuman How did you come up with this?
brooom its not o(1) its log(n)
BlackVS It is really O(1) - just take one log2 and few other simple math operations. Loop is really needn't at all. One hint - in each column sum of index and value is constant.
wohlwendk I'm late, but if we assume multiplication and addition to be O(1), the logarithm function is still O(log n). Since we have hardware acceleration for the logarithm, it's still faster than the iterative solution, but only by a constant factor
nikhilkuria Really implore fellow coders not to paste readymade solution in the board.
This is a real nice problem. If you can understand how the value is calculated and can find a pattern in there, you are already there.
shintoishere but too much math
ajayvembu No! Anybody could explain the concept or the Math involved but not the working code, which is like giving away.
shubshubham256 my solution is passing 7 test but its fail for 4 tests ..in those input were ig no so i hv used long bt its not working
shubshubham256 - #include
- using namespace std;
- int main(){
- int t,d=3, m=3,p;
- cin >> t;
- int a[t];
- int n=t;
- for(int i=1;i<=n;i++)
- {
- p=d;
- a[i]=p;
- if(d==1)
- {d=m*2;
- m=d;
- d++;}
- d--;
- if(i==n)
- cout<
- }
- return 0;
- }
lukes712 Same here. When I run the 4 failed tests manually, my solution is correct.
shubshubham256 OKK
ngtrnhan1205 You guys have not noticed the constraints: t <= 10^12.
Your code can not to solve the problem in few seconds.
juharri3 Try using a 64 bit integer.
sharmaparthyoge1 Try this one in java. Solution with Time complexity O(log2n)
static long strangeCounter(long t) { long p1 = 0; long p2 = 3; long p3 = 3; while(p1<=t){ if(t<=p2 && t>p1){ break; } else{ p1 =p2; p3 = p3*2; p2 = p2+p3; } } long tmp = p2-p1; long ans = 0; if(p1+1==t){ ans = tmp; } else if(p2==t){ ans = 1; } else{ ans = p2-t+1; }
return(ans); }
balajivenjix Yes it is a nice problem..Good work to brain and simple if we understand the logic...
tao_zhang A Java solution:
import java.util.Scanner; public class StrangeCounter { public static void main(String[] args) { Scanner in = new Scanner(System.in); long t = in.nextLong(), n = 2; while (3 * (n - 1) < t) n = 2 * n; System.out.println((3 * (n - 1) - t + 1)); } }
hamza_emra Could you please explain
tao_zhang As you may have noticed, brute force algoritm is too slow to pass all tests for this problem. So we need to find a faster way to solve this problem. For these type of questions which has lots of numbers and follows some rule while it's growing, more offen than not, there is a math pattern that will work. Normally, we just have to write down a general enough example somewhere to find out what is the pattern. For example, if you are in an interview you need to think in this way and write your own cycles. Now, since there already are examples of the first three cycles in the description, we'll just use that instead ... but I digress.
If you look carefully, the last 'time' value of cycle 1 is 3 which is 3*1=3*(2^1-1), the last 'time' value of cycle 2 is 9 which is 3*3=3*(2^2-1), the last 'time' value of cycle 3 is 21 which is 3*7=3*(2^3-1).
So, we should keep doubling n, which represents the 2^1, 2^2, 2^3 part. Hence the while loop. The loop stops when it reaches to a cycle whose max time is bigger than the real time t, then we know that it has reached the last cycle.
And taking the second cycle as an example, 'time' 7 has 'value' 3, and the max time of the second cycle is 9. We find the relationship between them is 3 = 9 - 7 + 1, which is why we print (3 * (n - 1) - t + 1) to get the output of 3 when t is 7.
ramesh_l Thanks, its helps me to understand clearly
hamza_emra Thanks
shubhDeColon Nicely explained, to do something is different than to explain.
kb2232 this still will fail test case. The point it to avoid looping
madhu703 thanks
avasansuman thanks for the explanation!!!!cheers!!
anamxali1 Thank you so much for that!
code18 You can just calculate the answer without the while loop:
val cycleLength = (Math.pow(2, log((t.toLong + 2) / 3, 2)) * 3).toLong; val answer = cycleLength + cycleLength - t - 2;Note that the log function, here, truncates to only the integer part (i.e., returns the floor of the log base 2).
At the start of each cycle, the value is 3 times some power of 2, and that value is t plus 2. Then each successive value decrements the starting value by one, until it reaches one, then a new cycle starts.
kb2232 this solution is wrong for some test cases.
bharath1992pr cool
BarrySW19 Don't post solutions here.
vvbhandare Such a Genius. Would like to get advice from you about improving logical skills.
saif01md it fails.
Akash_Mishraa bro can you give me any idea how devlop my algorithmic skill.
AnonymousCam A closed form solution is possible. You can calculate which column the t is in. From that you can calculate what the 1st time and value in that column will be. After that, calculating the value corresponding to t is trivial.
Hint: Notice that the number of elements in each column form a geometric series: 3, 6, 12, ..., 3 * 2^(column - 1)
You can use (or derive) the formula for the sum of a geometric series to figure out how many elements there are, in total, in the 1st n columns.
robert20paul O(1)
public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); long t = in.nextLong(); long x = (t + 2) / 3; long b = Long.highestOneBit(x); long tb = 3 * b; System.out.println(tb - (t - (tb - 2))); } }
codertoaster Please explain this solution. What does Long.highestOneBit(x) do ? And how did you come up with this solution.
rigobrinkman Absolutely beautiful, using highestOneBit over log makes it so clean.
koolmukul Simple understandable O(log n) solution. Passing all Test cases.
def strangeCounter(t): curr_cycle = 1 curr_time = 1 prev_time = 1 while(curr_time<= t): prev_time = curr_time prev_value = 2**(curr_cycle-1)*3 curr_time = curr_time + prev_value curr_cycle+=1 return prev_value - (t-prev_time)
Istros I don't know if this is good or not(O(log n)) but here is a simple Python solution.
def strangeCounter(t): lst = [1] while lst[-1] <= t: lst.append(2 * lst[-1] + 2) return lst[-1] - t
ayubansal1998 it's pretty simple code with complexity of O(1) without any loop
int main(){ long long int t,a,b; cin >> t; a=ceil(log2 (1.0*(t+3)/3)); b=3*(pow(2,a)-1); a=b-t+1; cout<<a; return 0; }
awanti2019 what is the use of 1.0 in log?
ayubansal1998 Because t+3 is an integer and (integer)/(integer) will give an integer value thus first we have to make it float and then divide to get exact value of (t+3)/3
alexanderatrank What killed me was that the "template" starts all over with int t = Convert.ToInt32(Console.ReadLine());
Thats a "bit" missleading as they use Long as input.
sungmkim80 This got me fail 4 tests... The template is wrong.
Sort 447 Discussions, By:
Please Login in order to post a comment