SGU Problem 105. Div 3 Solution

Problem Description :
    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.





Solution :
See this pattern :

• 1 is not divisible by 3.
• 1 + 2 = 3 is divisible by 3. 
• 1 + 2 + 3 = 6 is divisible by 3.
• 1 + 2 + 3 + 4 = 10 is not divisible by 3. 
• 1 + 2 + 3 + 4 + 5 = 15 is divisible by 3. 
• 1 + 2 + 3 + 4 + 5 + 6 = 21 is divisible by 3.  
• 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 is not divisible by 3.
•  
•  
• 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 is divisible by 3. 
• 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0) = 46 is not divisible by 3. 
• 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0)  + (1 + 1) = 48 is divisible by 3.

 Have you got any idea. If not see the solution.Here is the C implementation of this problem.

 

#include <stdio.h>

int main(){
 long i,j,k,l,tmp,n,ans;

 while( scanf("%ld", &n) == 1){  
  ans = n/3;
  ans <<= 1;

  if( (n%3) ){
   ans += (n%3) - 1;
  }
  printf("%ld\n",ans);
 }
 return 0;
}