binary clock

[xgeutzu]

this is the problem:

A binary clock is a clock which displays sexagesimal time (military format) in a binary format. There are also two kinds of representations for a binary clock; vertical or horizontal.

Below is the horizontal representation of the time 10:37:49

(H) 0 0 1 0 1 0 (10)
(M) 1 0 0 1 0 1 (37)
(S) 1 1 0 0 0 1 (49)
so when it is grouped together as a binary string, it looks like this:

001010 100101 110001
Find the total number of 1s in the representations of military time for a full 24 hour period which elapses from 00:00:00 to 23:59:59. How many total 1s appear for the entire year (a regular 365 day year)?


and this is my code, but when I enter the result on their site it told me that is a wrong answer ! any idea somebody ?

#include <iostream>

using namespace std;

int s_hour=0, s_min=0, s_sec=0;

int binary_counting(int x)
{
    int c=0, a[100], count = 0;
    while(x!=0){
        a[c]=x%2;
     c++;
     x=x/2;
    }

    for(int i=0;i<=c-1;i++)
       if(a[c-1-i] == 1) count++;

    return count;
}

int main()
{
    for(int i=0;i<24;i++)
        s_hour+=binary_counting(i); //sum for 24h er a day

    for(int i=0;i<60;i++)
    {
        s_min+=binary_counting(i); //sum for 60 min per hour
        s_sec+=binary_counting(i); //sum for 60 sec per min
    }

    int day = s_hour + 24 * s_min + 1440 * s_sec; // make the sum for a day

    cout << day*365; // year
}

[AbstractionAnon]

As I read the instructions, you need to iterate through all 86,440 86,400 seconds in a day and count the ones in each display.

[xgeutzu]

s_sec memorize how much 1s are in binary transformation for numbers from 0 to 59.
then I multiply the result with 1440, because there are 1440 minutes on a day, so the clock seconds will loop from 0 to 59, 1440 times.

and there are 86,400 seconds on a day, not 86,440.

thanks you for your relpy.

[AbstractionAnon]

My point was there are 86,400 unique values that the clock displays per day.

I believe that the instructions are asking how many 1's are displayed for the 86,400 unique values of the 18 binary digits. Your calculation at line 33 does not account for that. You're counting the number of 1 bits in each of the 23 hours only once. Of course, that is only my interpretation of the instructions.

[xgeutzu]

aaAAA... I got your point. so i modify the program, and now it transform in binary all numbers from 0 -> 235959 (no ALL numbers.. just all numbers generate by clock-rule) , and for each binary transformation in add to sum the the numbers of 1. still don't get the right result. ideas ?

#include <iostream>
#include "windows.h"

using namespace std;

int binary_counting(int x)
{
    int c=0, a[100], count = 0;
    while(x!=0){
        a[c]=x%2;
     c++;
     x=x/2;
    }

    for(int i=0;i<=c-1;i++)
       if(a[c-1-i] == 1) count++;

    return count;
}

int main()
{
    int sec=0, min=0, hour=0, clock=0, sum=0;


    while(true)
    {
       clock = hour*10000 + min*100 + sec;
       cout << clock << endl;
       if(GetAsyncKeyState(VK_F2)) system("pause");
       sum+=binary_counting(clock);
       sec = sec + 1;
       if(sec==60)
       {
           sec=0;
           min = min + 1;
           if(min==60)
           {
               min=0;
               hour = hour + 1;
               if(hour==24) break;
           }
       }

    }

    cout << sum << endl;
}

[whitenite1]

@xgeutzu

Remember, any number multiplied by zero, will equal zero. Try changing the declarations of sec, min and hour from a zero, to a one.

[AbstractionAnon]

Do you know the correct result?
What's the link to the site to test your program?
Does the site time your code to preclude a brute force approach?

When I run it with a brute force approach using std::bitset<6> for each segment, I get an answer of 682,560.

Your line 31 is not correct. You're treating clock as a single binary number. It's not. The clock is made up of three 6 bit segments. One each for hour, minute and second. The number of bits in each segment is independent.

@whitenite1 - Why is that an issue? Counting hours from 1 to 24 instead of 0 to 23 won't give you the right binary values and hence not the correct answer.

[booradley60]

I got 682,560 as well.

@xgeutzu: Your binary_counting function is way too complicated for what it does, but I think it works. So, assuming that it works, the rest should be as simple as this (brute force):

[pseudocode]
numberOfOnes = 0
for(hour = 0 -> 23)
    for(minute = 0 -> 59)
        for(second = 0 -> 59)
            numberOfOnes += binary_counting(hour)
            numberOfOnes += binary_counting(minute)
            numberOfOnes += binary_counting(second)

Optimization suggestions
If you need it to go faster, just calculate and cache the results of binary_counting on numbers 0-59, since those are the only ones you ever use:

    //cache off the range of relevant values instead of recalculating everytime
    int count_of_ones[60];
    for(int i = 0; i < 60; ++i)
    {
        count_of_ones[i] = binary_counting(i);
    }
    //...
    numberOfOnes += count_of_ones[hour];

You can also calculate the sum of number of ones that each hour contributes, then multiply that value by 3600, since each hour is shown in 3600 unique time slots. (each hour number is shown for 60 minutes, 60 seconds in each of those minutes, 60*60 = 3600) Recall that

  count_of_ones[0] * 3600
+ count_of_ones[1] * 3600
+ count_of_ones[2] * 3600
+...
+ count_of_ones[23] * 3600

equals

(count_of_ones[0] + ... + count_of_ones[23]) * 3600 

so you only have to do the multiplication once.

The same optimization can be done for minutes and seconds. However, each minute number is shown 1440 unique times. (Any given minute number is shown once per hour, for a duration of 60 seconds, 24*60 = 1440.) The same applies to seconds.

Calculating the contribution of ones by each hour number, minute number, and second number like this reduces the amount of looping you'd otherwise have to perform.

Hold off on optimizing until you're sure you've reached the correct solution with the straight-forward, brute-force method.

[xgeutzu]

thank you guys for reply !

I solve it. The problem with my first code, was that i didn't calculate that the hour is printed every second. With the code below I got the correct answer :

#include <iostream>

using namespace std;

int binary_counting(int x)
{
        int count = 0;
        while(x!=0)
        {
            count += (x &amp; 1);
            x=x/2;
        }

        return count;
}

int main()
{
    int sec=0, min=0, hour=0, clock=0, sum=0;


    while(true)
    {
        sum = sum + binary_counting(hour);
        sum = sum + binary_counting(min);
        sum = sum + binary_counting(sec);
        sec = sec + 1;
        if(sec==60)
        {
            sec = 0;
            min = min + 1;
            if(min==60)
            {
                min = 0;
                hour = hour + 1;
                if(hour==24) break;
            }
        }

    }

    cout << sum*365 << endl;
}

@Abstraction Anon, this is the site: http://www.cstutoringcenter.com/ problem 52