# Strange Counter

# Strange Counter

sreejith_menon + 49 comments 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 + 1 comment Can you explain your code

s92014721 + 0 comments Basically you find where the closest 1 is and subtract out the difference from the actual t.

laymann + 1 comment You are awesome!

sreejith_menon + 0 comments Thank you! :)

sachin_hg + 3 comments Can this be any simpler !!! :)

BlackVS + 6 comments Yes. No loops. Only few math ops. https://www.hackerrank.com/challenges/strange-code/submissions/code/36756057

Ridhuvarshan + 0 comments Cool. I forgot math, so i can't do stuff like this :p

atreidex + 0 comments same as my solution. but power and log functions also has loops.

malli9603112487 + 1 comment what is that math formula .i figured that in every cycle second element be same .but unable to construct formulae

josef_klotzner + 1 comment 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 + 0 comments Start with the base values (using python here) and given

`t`

`t = 1, 4, 10, 22... v = 3, 6, 12, 24...`

=>`t = 3 * 2**n - 2`

We can solve for

`n`

`n = math.log2((t + 2) / 3)`

We can get the base value

`Bv`

of all`t`

by flooring`n`

`Bv = 3 * 2**(n//1)`

Next look at the sequence

`t = 10, 11, 12, 13... v = 12, 11, 10, 9...`

`v`

is twice the base value of each sequence minus`t`

minus 2`v = 2 * Bv - t - 2`

So we can solve with

`int(6 * 2**(math.log2((t + 2) / 3) // 1) - t - 2)`

borisov_andrew_a + 1 comment Only math and less math https://www.hackerrank.com/challenges/strange-code/submissions/code/80406038

x_curveball_x + 0 comments test case 1 is not satisfied

groote + 0 comments how to see your code as soon as i click on this link new page open then just got dissappered

x_curveball_x + 0 comments test case 1 is not satisfied

debasis_jana_iit + 1 comment 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 + 2 comments Can you explain. This is very nice.

debasis_jana_iit + 1 comment 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 + 0 comments Correction: 3, 6, 12*

amdokamal + 0 comments 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 + 0 comments Exactly what Chandler would've said!

hemendrav4 + 0 comments You are awesome! Thank you! :)

ppprockrahul + 0 comments It's work but why u use -t+1 as in every case at last t will be 1

learner_codes + 0 comments splendid :)

LouManChuu + 0 comments Wow. I knew I was overcomplicating things. You did in 5 lines what took me about 50. Very elegant. Beautiful.

mboros + 3 comments I came up with the same solution in C++ and I was getting time outs on several test cases

MrAsimov + 1 comment same solution in C.it passed all test cases.

Damster + 2 comments In C++,

while(t>lower+upper-1) // lower = 1 , upper = 3 lower+=upper, upper*=2; cout<<upper-(t-lower);

quachtridat + 0 comments 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 + 0 comments mine had the same approach

Damster + 0 comments [deleted]aleksei_maide + 0 comments had timeouts in C++ until changed to long instead of int... i guess the while statement didnt end with int's range...

PortgasAce + 0 comments [deleted]PortgasAce + 2 comments Does it pass all test cases ? I doubt

marigabibenitez + 0 comments [deleted]sreejith_menon + 0 comments It does. You can try it too.

krishnna + 0 comments really very nice logic

mananrajn + 0 comments Simply amazing man...and here i was stuck trying to solve it in such a complex way...Kudos !

zehranur + 0 comments this is awesome!!

vvbhandare + 0 comments Getting timeout for TC - 4, 5, 6, 8

kb2232 + 1 comment It is not Big-O (log n). It will not pass all test case

sreejith_menon + 0 comments It passes all the test cases and for each iteration, n is cut down in half. Hence a

`log`

complexity.

shubshubham256 + 2 comments stupid man!!!! its giving wrong answer.

kb2232 + 0 comments 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 + 0 comments Thank you for your comment. :) Why the rage sir?

I passed all the test cases.

x_bcn23 + 0 comments [deleted]bgreenfield + 0 comments my solution was identical save in another progamming language.

Forbidden_Devil + 0 comments That is amazing... I always wish to come up with a solution like this..

bharatherukulla + 0 comments awesome

bgreenfield + 0 comments 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 + 0 comments what about t=10

piyushjaisingkar + 0 comments You are really good. #Respect.

soumyadas047 + 0 comments Great Solution

Amsaveni + 0 comments You are great!

CCWorldTraveler + 0 comments 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 + 0 comments Awesome :)

wryan42675 + 1 comment 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 + 0 comments 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 + 0 comments I made the same approach.

:-)

ajayknit2011 + 0 comments 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 + 0 comments **SIMPLY AWESOME**Tsvetoslav88 + 0 comments The solution is working but I can't catch the logic for the solution

bdchambers79 + 0 comments That was my first solution, but it times out in C#

VikashOP + 0 comments That is awesome !!!

nadiyakhurshid98 + 0 comments some testcases went timed out !

Tandilashvili + 0 comments 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 + 0 comments never thought of doing it this way. My approach was a lot longer;

NoneCares + 0 comments WOW

imskv420 + 0 comments 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 + 0 comments Genius level intellect ! Coming to a conclusion to there is a pattern is fine. But to execute it with such ease, nice

liuyuhao717 + 0 comments 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 + 0 comments Amazing!

sarathy_v_krish1 + 0 comments 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 + 0 comments 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 + 0 comments your logic is so awesome

Iqra77777saleem + 0 comments can you explain how this solution is in log n

pawansinghla + 0 comments How can you think this approch.

mogonen + 0 comments genius...

kumarsurajsingh1 + 0 comments Its very optimize. good

wooddoo + 2 comments 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 + 1 comment 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 + 0 comments How did you come up with this?

brooom + 1 comment its not o(1) its log(n)

BlackVS + 1 comment 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 + 0 comments 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 + 3 comments 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 + 1 comment but too much math

ajayvembu + 0 comments No! Anybody could explain the concept or the Math involved but not the working code, which is like giving away.

shubshubham256 + 4 comments 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 + 0 comments - #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 + 1 comment Same here. When I run the 4 failed tests manually, my solution is correct.

shubshubham256 + 1 comment OKK

ngtrnhan1205 + 0 comments You guys have not noticed the constraints: t <= 10^12.

Your code can not to solve the problem in few seconds.

juharri3 + 0 comments Try using a 64 bit integer.

sharmaparthyoge1 + 0 comments 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 + 0 comments Yes it is a nice problem..Good work to brain and simple if we understand the logic...

tao_zhang + 7 comments 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 + 1 comment Could you please explain

tao_zhang + 7 comments 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 + 0 comments Thanks, its helps me to understand clearly

hamza_emra + 0 comments Thanks

shubhDeColon + 0 comments Nicely explained, to do something is different than to explain.

kb2232 + 0 comments this still will fail test case. The point it to avoid looping

madhu703 + 0 comments thanks

avasansuman + 0 comments thanks for the explanation!!!!cheers!!

anamxali1 + 0 comments Thank you so much for that!

code18 + 1 comment 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 + 0 comments this solution is wrong for some test cases.

bharath1992pr + 0 comments cool

BarrySW19 + 0 comments Don't post solutions here.

vvbhandare + 0 comments Such a Genius. Would like to get advice from you about improving logical skills.

saif01md + 0 comments it fails.

Akash_Mishraa + 0 comments bro can you give me any idea how devlop my algorithmic skill.

AnonymousCam + 1 comment 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 + 2 comments 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 + 0 comments Please explain this solution. What does Long.highestOneBit(x) do ? And how did you come up with this solution.

rigobrinkman + 0 comments Absolutely beautiful, using highestOneBit over log makes it so clean.

koolmukul + 0 comments 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 + 0 comments 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 + 1 comment 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 + 1 comment what is the use of 1.0 in log?

ayubansal1998 + 0 comments 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 + 1 comment 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 + 0 comments This got me fail 4 tests... The template is wrong.

Sort 447 Discussions, By:

Please Login in order to post a comment