none
COJ.UCI questions RRS feed

  • Question

  • question:

    There is sequence 1, 12, 123, 1234, ..., 12345678910, .... Given first N elements of that sequence. You must determine amount of numbers in it that are divisible by 3.

     

    my solution:

     

    #include <iostream>
    using namespace std;

    int main()
    {
        long long n, number;
        long long divx3count;
        while(cin >>n)
        {
                  divx3count=0;
              number = 0;
              for(long long count = 1;count <= n;count+=1)
                {
                      number = number + count;
              if(number % 3 == 0)
               {
                divx3count++;
                }
                     }
                    cout << divx3count << endl;
         }
             
        return 0;
    }

     

    its taking too long to process exeeding the time limit which is 100MS my current time limit is 109MS

    Monday, November 15, 2010 11:28 PM

Answers

  • Hi,

    first of all is that no certification related question. It is a c++ related question so I would suggest to use a C++ forum to ask this question.

    But I can try to help you a little.

    First of all: Yes, your code is already quite good but it is not working correctly.

    First of all, the sequence is:

    1, 12, 123, 1234, ....

    But what you did in code is more or less the calculation of the checksum, so instead of the 12, you check the number 3, instead of 1234 you check the 10, ... That is a good optimisation to get a quicker calculation.

    But you are not calculating the checksum correctly. So instead of adding 10, you have to add 1, instead of 11 you have to add 2 and so on ...

    So maybe you can optimize this a little more so you keep smaller numbers.

    Another trick could be: Whenever number % 3 is 0, you set number to 0. The only check you want to do is this %3. And you have something like (a + b) / 3 which is a / 3 + b / 3 and when you know, that a % 3 = 0, and you are only interested in modulo operations you can leave it out.
    (OK - do not make the fault to write (a+b) % 3 = a%3 + b%3! That is simply wrong: 2%3 + 2%3 = 4 and 4%3 = 1!)

    That way the calculation is again a little quicker, because the number is smaller. And instead of a long long you can use a smaller type. The input n should also be a smaller type, because a high long long will cause an overrun when you add more numbers to it! But that is some other point ...

    Ok, now we have a closer look at the checksum.

    The checksums are
    1 (1)
    3 (1 + 2)
    6 (1 + 2 + 3)

    10 (1 + 2 + 3 + 4       = 1 + 2 + 3 + 1 + 3)
    15 (1 + 2 + 3 + 4 + 5 = 1 + 2 + 3 + 1 + 2 + 2*3)
    ...

    So what do we see now? First we said, that we can set something to 0 when it can be divided by 3. So now I simply remove all 1 + 2 +3:

    1 (1)
    3 (1 + 2)
    6 (1 + 2 + 3)

    10 (4       = 1 +       1*3)
    15 (4 + 5 = 1 + 2 + 2*3)

    When we check something %3 only, we can get rid of a*3 inside (something I wrote above!)

    So now we see, that the sequence is simply:
    (1)
    (1+2)
    (1+2+3)

    (1)
    (1+2)
    (1+2+3)

    (1)
    (1+2)
    (1+2+3)

    ...

    So now we see the patern: - + + - + + - + + - + + ...! So now we can calculate it directly!

    In 3 tests, we get 2 hits. So first we simply calculate n / 3 * 2 (in each full 3 tries, we get 2 numbers that can be divided by 3!)

    But we are not finished: 1/3 = 0 -> ok. 2/3 = 0 Wrong - for 2 numbers we get 1 hit. 3/3 = 1 - times 2: correct. You can check that further. So whenever n % 3 is 2, we have to add 1.

    So the code can be simply:
    divx3count = n / 3;
    if (n % 3 = 2) divx3count++;

    And then you are done.

    I hope i was able to explain everything. That is now really the fastest solution you can get without any iteration.

    Konrad

    Tuesday, November 16, 2010 6:34 AM
    Answerer
  • Maybe some other explanation also helps. You are adding something to a number and always calculate % 3.

    Instead of "i set it 0 if the modulo result is 0" you can simply set it to "I set it to the result of the % operation".

    The mathematic rule with % is:

    (a + b) % c = (a%c + b%c) % c

    This is hard to be proven. It can be shown through the (a + b) / c = a/c + b/c rule. But the problem I have is, that % is more of a rule how to calculate than a real operation in my eyes. So with the proove I have some problems.

    So now we simply check the % values of the numbers you add. And then you see, it is always 1, 2, 0, 1, 2, 0, ....

    So 1 + 2 is 3 so % is 0 again. Adding 3 to a number that can be divided by 3 changes nothing. So that also shows the rule.

    or if you have to proove it to your teacher, you can simply do it this way:

    Simply write down the first 20 numbers with the results. Then you see the rule and you can calculate the result, too.

    Hope I was able to write it in a way that you was able to understand.

    Konrad

    • Marked as answer by Jblacks Thursday, December 30, 2010 9:22 PM
    Tuesday, November 16, 2010 6:41 AM
    Answerer

All replies

  • Hi,

    first of all is that no certification related question. It is a c++ related question so I would suggest to use a C++ forum to ask this question.

    But I can try to help you a little.

    First of all: Yes, your code is already quite good but it is not working correctly.

    First of all, the sequence is:

    1, 12, 123, 1234, ....

    But what you did in code is more or less the calculation of the checksum, so instead of the 12, you check the number 3, instead of 1234 you check the 10, ... That is a good optimisation to get a quicker calculation.

    But you are not calculating the checksum correctly. So instead of adding 10, you have to add 1, instead of 11 you have to add 2 and so on ...

    So maybe you can optimize this a little more so you keep smaller numbers.

    Another trick could be: Whenever number % 3 is 0, you set number to 0. The only check you want to do is this %3. And you have something like (a + b) / 3 which is a / 3 + b / 3 and when you know, that a % 3 = 0, and you are only interested in modulo operations you can leave it out.
    (OK - do not make the fault to write (a+b) % 3 = a%3 + b%3! That is simply wrong: 2%3 + 2%3 = 4 and 4%3 = 1!)

    That way the calculation is again a little quicker, because the number is smaller. And instead of a long long you can use a smaller type. The input n should also be a smaller type, because a high long long will cause an overrun when you add more numbers to it! But that is some other point ...

    Ok, now we have a closer look at the checksum.

    The checksums are
    1 (1)
    3 (1 + 2)
    6 (1 + 2 + 3)

    10 (1 + 2 + 3 + 4       = 1 + 2 + 3 + 1 + 3)
    15 (1 + 2 + 3 + 4 + 5 = 1 + 2 + 3 + 1 + 2 + 2*3)
    ...

    So what do we see now? First we said, that we can set something to 0 when it can be divided by 3. So now I simply remove all 1 + 2 +3:

    1 (1)
    3 (1 + 2)
    6 (1 + 2 + 3)

    10 (4       = 1 +       1*3)
    15 (4 + 5 = 1 + 2 + 2*3)

    When we check something %3 only, we can get rid of a*3 inside (something I wrote above!)

    So now we see, that the sequence is simply:
    (1)
    (1+2)
    (1+2+3)

    (1)
    (1+2)
    (1+2+3)

    (1)
    (1+2)
    (1+2+3)

    ...

    So now we see the patern: - + + - + + - + + - + + ...! So now we can calculate it directly!

    In 3 tests, we get 2 hits. So first we simply calculate n / 3 * 2 (in each full 3 tries, we get 2 numbers that can be divided by 3!)

    But we are not finished: 1/3 = 0 -> ok. 2/3 = 0 Wrong - for 2 numbers we get 1 hit. 3/3 = 1 - times 2: correct. You can check that further. So whenever n % 3 is 2, we have to add 1.

    So the code can be simply:
    divx3count = n / 3;
    if (n % 3 = 2) divx3count++;

    And then you are done.

    I hope i was able to explain everything. That is now really the fastest solution you can get without any iteration.

    Konrad

    Tuesday, November 16, 2010 6:34 AM
    Answerer
  • Maybe some other explanation also helps. You are adding something to a number and always calculate % 3.

    Instead of "i set it 0 if the modulo result is 0" you can simply set it to "I set it to the result of the % operation".

    The mathematic rule with % is:

    (a + b) % c = (a%c + b%c) % c

    This is hard to be proven. It can be shown through the (a + b) / c = a/c + b/c rule. But the problem I have is, that % is more of a rule how to calculate than a real operation in my eyes. So with the proove I have some problems.

    So now we simply check the % values of the numbers you add. And then you see, it is always 1, 2, 0, 1, 2, 0, ....

    So 1 + 2 is 3 so % is 0 again. Adding 3 to a number that can be divided by 3 changes nothing. So that also shows the rule.

    or if you have to proove it to your teacher, you can simply do it this way:

    Simply write down the first 20 numbers with the results. Then you see the rule and you can calculate the result, too.

    Hope I was able to write it in a way that you was able to understand.

    Konrad

    • Marked as answer by Jblacks Thursday, December 30, 2010 9:22 PM
    Tuesday, November 16, 2010 6:41 AM
    Answerer
  • yea thanks this helped alot also i am seeing where it reduced the amount of memory the program took......thnx again
    Tuesday, November 16, 2010 4:42 PM