# Strange Counter

# Strange Counter

sreejith_menon + 58 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 + 2 comments Can you explain your code

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

sauravgpt + 1 comment please explain it briefly

radu_lupaescu + 1 comment You have to search for the cycle your given time is in. First cycle has 3 "slots", second has 6 and so on..

ex: if T is 14, we remove the first cycle => 11, is there room for a full next cycle? (2 * 3) if so, remove the second cycle from 11 => 5. is there room for next cycle? if not, count backwards from the starting point.

vishalbty + 0 comments For anyone looking for an answer with indepth explanation.Here you go.

johndoncowan + 0 comments It's pretty straightforward:

- The counter begins at 3. Each time it would tick down to zero, it instead “loops” up to double its previous maximum value, represented by "rem *= 2".
- "t = t-rem" represents the counter ticking down before reinitializing. By subtracting the counter’s current maximum value directly from the remaining timer, we can skip looping the counter ticking "t" times, instead only following the number of times the counter itself loops back up from 0 within the bounds of t.
- Once the remaining timer is less than the maximum counter, you’re in the final “loop” of the counter. The output is the value remaining on the counter once the timer runs out.

laymann + 2 comments You are awesome!

sreejith_menon + 0 comments Thank you! :)

prakhar123mishra + 1 comment hey please help me also.. my program is unable to work when t is 10000000 , termination time out occurs, what should i do?

swatilekha_roy4 + 0 comments Initialize rem with data type long, instead of int. Hope it fixes your problem!

sachin_hg + 5 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 + 1 comment 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)`

qayum_khan_usa + 0 comments My one-line

**Python3**code was nearly identical but without`//1`

.def strangeCounter(t): return 6 * 2**int(math.log2( (t+2)/3 )) - (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!

ams200140 + 0 comments main = readLn >>= print . (+1) . f 0

f n x | x > 3*(2^n) = f (n+1) (x-3*(2^n)) | otherwise = 3*(2^n) - x

sr_hossain + 0 comments `long long int nn;cin>>nn; long long int a=log2(--nn/3.+1)+1; a=3*(pow(2,a)-1); cout<<a-nn<<endl;`

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 + 1 comment This is much more efficient way:

function strangeCounter($t) { $scnt = 3; while ($t+2 >= $scnt) $scnt *= 2; $scnt /= 2; return $scnt-($t - $scnt+2); }

kirtipurohit025 + 1 comment which language is this?

dilipagarwal001 + 0 comments [deleted]

Rishabh510 + 0 comments never thought of doing it this way. My approach was a lot longer;

NoneCares + 0 comments WOW

imskv420 + 1 comment 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)

raveen_gatla + 0 comments Nice CODE with simple execution

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 + 1 comment 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

abhi03jan + 1 comment use long rate=3;

all test case will pass for sure.

lemanisar23 + 0 comments thank you so much!!!!!!

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

Singhalr31 + 0 comments how u guys think like this??am still not getting it even after seeing this solution?? :( :,(

kris_tobiasson + 0 comments Here is my JS approach, very similar:

let timer = 3; while(t > timer){ timer = timer * 2 + 3; } return timer - (t-1);

christine_lyn_c1 + 0 comments Had the same solution but in C#. For some reason I still get runtime errors. Switched to Python using my same solution and it passed just fine. :/

madhavmishra28 + 0 comments It didn't work because of timeOut problem in few test cases. WHY ???

mohit_srv + 0 comments How you think like this man

Thundergod_Thor + 0 comments Hey c, c++ guys out there ! Use long long int to store values of integers related to t if you are going through the above code logic.

dilipagarwal001 + 0 comments It can be done in O(1) like this

long strangeCounter(long t) {

`long n = ceil(log((t+3)/3.0)/log(2)); return 6*pow(2, n-1) - t -2;`

}

deepakshiarora8 + 0 comments it does not pass all testcases in cpp

Aditi_Pandey + 0 comments that's awesomesauce!!

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

yerzhik + 0 comments sequence is t = 3 + 3 * 2 + 3 * 2^2 + ... 3 * 2^n + remainder r = remainder t = 3 * (2^(n + 1) - 1) + r t >= 3 * (2^(n + 1) - 1) n <= log2(t/3 + 1) - 1 that's how u estimated max n full cycles

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 + 1 comment 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

jakub_bielecki + 0 comments Yes the problem requires to calculate a logarithm. But calculating logarithm of integer parameter is O(log log n). This is even without hardware optimizations. It's much much less than O(log n).

And there

*are*hardware optimizations, becuase this particular problem really only requires to tell "how many leading zero bits are there in a 64-bit integer?". If you try 64 iterations to check that, well, I can certainly see room for improvement.

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 + 8 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!

abdulraheemabid + 0 comments Thank you. Amazing and simple explaination.

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.

Sort 590 Discussions, By:

Please Login in order to post a comment