Mfcttrf

How to tell readers that I know my story is factually incorrect?

Is encryption still applied if you ignore the SSL certificate warning for self-signed certs?

How was Luke's prosthetic hand in Episode V filmed?

Why do we need an estimator to be consistent?

What could make large expeditions ineffective for exploring territory full of dangers and valuable resources?

You have no, but can try for yes

What is the function of "mal" in saying "Das nenn ich mal ein X"?

What is the intuition for higher homotopy groups not vanishing?

How should I interpret a promising preprint that was never published in a peer-reviewed journal?

What's the largest an Earth-like planet can be and support Earth's biosphere?

Somebody hacked my clock

Did Hitler say this quote about homeschooling?

How important are the Author's mood and feelings for writing a story?

To what extent does asymmetric cryptography secure bitcoin transactions?

Why would word of Princess Leia's capture generate sympathy for the Rebellion in the Senate?

Could a US citizen born through "birth tourism" become President?

Which modern firearm should a time traveler bring to be easily reproducible for a historic civilization?

Replacing light switches and outlets without electrical boxes

Linux ext4 restore file and directory access rights after bad backup/restore

I want light controlled by one switch, not two

Does unblocking power bar outlets through short extension cords increase fire risk?

Why are flying carpets banned while flying brooms are not?

I have found a mistake on someone's code published online: what is the protocol?

When we are talking about black hole evaporation - what exactly happens?

Counting multiples of 3 up to a given number

SPOJ “SBANK - Sorting Bank Accounts” TLEOptimal way to annihilate a list by removing items from the endsCounting number of inversionsCount the number of inversions using Binary Indexed Tree in an arrayTime Limit Exceeded for ETF - Euler Totient Function at SpojCounting pairs of integers whose sum is less than a given thresholdCodeChef PRIME1 problem in PythonOptimised Python Code gives TLE for PRIME1Count numbers with atleast one common factor, excluding oneSplit a given number so that their sum adds to another given number

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

4

$begingroup$

I'm attempting a practice problem in Codeforces that requires you to find the number of multiples of 3 less than or equal to a given number. I have written the following code but it gives a TLE once the test case reaches the order of 10⁸.

int x = Reader.nextInt();
int count = 0;

for(int i = 3; i<=x; i++)
 if(i%3 == 0)
 count++;
 

System.out.println(count);

Is there any way I can further optimize this code? The test cases max out at 10⁹.

java programming-challenge time-limit-exceeded

share|improve this question

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  Can you think of a simple mathematical formula which computes the result directly, without the need for a loop?
  $endgroup$
  – Martin R
  12 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Is it dividing the given number by 3? Oh no
  $endgroup$
  – therealshankman
  12 hours ago
  

  
  
  
  

add a comment | 

4

$begingroup$

I'm attempting a practice problem in Codeforces that requires you to find the number of multiples of 3 less than or equal to a given number. I have written the following code but it gives a TLE once the test case reaches the order of 10⁸.

int x = Reader.nextInt();
int count = 0;

for(int i = 3; i<=x; i++)
 if(i%3 == 0)
 count++;
 

System.out.println(count);

Is there any way I can further optimize this code? The test cases max out at 10⁹.

java programming-challenge time-limit-exceeded

share|improve this question

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  Can you think of a simple mathematical formula which computes the result directly, without the need for a loop?
  $endgroup$
  – Martin R
  12 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Is it dividing the given number by 3? Oh no
  $endgroup$
  – therealshankman
  12 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

I'm attempting a practice problem in Codeforces that requires you to find the number of multiples of 3 less than or equal to a given number. I have written the following code but it gives a TLE once the test case reaches the order of 10⁸.

int x = Reader.nextInt();
int count = 0;

for(int i = 3; i<=x; i++)
 if(i%3 == 0)
 count++;
 

System.out.println(count);

Is there any way I can further optimize this code? The test cases max out at 10⁹.

java programming-challenge time-limit-exceeded

share|improve this question

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

int x = Reader.nextInt();
int count = 0;

for(int i = 3; i<=x; i++)
 if(i%3 == 0)
 count++;
 

System.out.println(count);

share|improve this question

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

edited 5 hours ago

mdfst13

18k66 gold badges2323 silver badges5858 bronze badges

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

New contributor

therealshankman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 12 hours ago

therealshankmantherealshankman

2855 bronze badges

3 Answers
3

active

oldest

votes

3

$begingroup$

If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:

for(int i = 3; i <= x; i += 3) 
 count++;

share|improve this answer

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  you missed a trick here, appending count++ in the loop
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah this works. I needed to count it as it was mentioned explicitly in the question. But I hadn't even figured the simple computation until a few minutes ago.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze how would that work?
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  for(int i = 3; i <= x; i += 3, count++);
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That “trick” doesn’t make the code run any faster, and can lead to errors if you forget/don’t notice the trailing semicolon. I would call it out reviewing other people’s code here on Code Review. I certainly didn’t “miss” it, and highly recommend against it. When iterating over a non-trivial body, with two or more iterators, incrementing all of them in the increment portion of the for() statement is proper, and can improve readability of the code.
  $endgroup$
  – AJNeufeld
  9 hours ago
  

  
  
  
  

 | 
show 2 more comments

2

$begingroup$

Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?

Your solution requires $O(x)$ time; it should be possible in $O(1)$.

share|improve this answer

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The title does state counting, not computing :p
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yep, I figured. I'll keep the question up as a reminder to me that most simple problems will have simple solutions.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That's only since someone butchered the title. It originally said finding.
  $endgroup$
  – mdfst13
  5 hours ago
  

  
  
  
  

add a comment | 

0

$begingroup$

If I were to compute the answer, I'd do (language shown is JavaScript):

var n = 1e8;
var v = Math.floor(n / 3);

6 has two multiples of three less than or equal to it: 6 / 3 == 2
127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.

Likewise, 3 * n will have n multiples of three, including three itself.

share|improve this answer

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm using Java here. Doing long/int division in Java ignores the decimal section anyways. But thanks for the answer, I'll keep it in mind for a later use.
  $endgroup$
  – therealshankman
  13 mins ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

therealshankman is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f224571%2fcounting-multiples-of-3-up-to-a-given-number%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:

for(int i = 3; i <= x; i += 3) 
 count++;

share|improve this answer

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  you missed a trick here, appending count++ in the loop
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah this works. I needed to count it as it was mentioned explicitly in the question. But I hadn't even figured the simple computation until a few minutes ago.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze how would that work?
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  for(int i = 3; i <= x; i += 3, count++);
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That “trick” doesn’t make the code run any faster, and can lead to errors if you forget/don’t notice the trailing semicolon. I would call it out reviewing other people’s code here on Code Review. I certainly didn’t “miss” it, and highly recommend against it. When iterating over a non-trivial body, with two or more iterators, incrementing all of them in the increment portion of the for() statement is proper, and can improve readability of the code.
  $endgroup$
  – AJNeufeld
  9 hours ago
  

  
  
  
  

 | 
show 2 more comments

3

$begingroup$

If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:

for(int i = 3; i <= x; i += 3) 
 count++;

share|improve this answer

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  you missed a trick here, appending count++ in the loop
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah this works. I needed to count it as it was mentioned explicitly in the question. But I hadn't even figured the simple computation until a few minutes ago.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze how would that work?
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  for(int i = 3; i <= x; i += 3, count++);
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That “trick” doesn’t make the code run any faster, and can lead to errors if you forget/don’t notice the trailing semicolon. I would call it out reviewing other people’s code here on Code Review. I certainly didn’t “miss” it, and highly recommend against it. When iterating over a non-trivial body, with two or more iterators, incrementing all of them in the increment portion of the for() statement is proper, and can improve readability of the code.
  $endgroup$
  – AJNeufeld
  9 hours ago
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:

for(int i = 3; i <= x; i += 3) 
 count++;

share|improve this answer

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

$endgroup$

for(int i = 3; i <= x; i += 3) 
 count++;

share|improve this answer

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

answered 11 hours ago

AJNeufeldAJNeufeld

10.2k11 gold badge88 silver badges3333 bronze badges

2

$begingroup$

Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?

Your solution requires $O(x)$ time; it should be possible in $O(1)$.

share|improve this answer

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The title does state counting, not computing :p
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yep, I figured. I'll keep the question up as a reminder to me that most simple problems will have simple solutions.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That's only since someone butchered the title. It originally said finding.
  $endgroup$
  – mdfst13
  5 hours ago
  

  
  
  
  

add a comment | 

2

$begingroup$

Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?

Your solution requires $O(x)$ time; it should be possible in $O(1)$.

share|improve this answer

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The title does state counting, not computing :p
  $endgroup$
  – dfhwze
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yep, I figured. I'll keep the question up as a reminder to me that most simple problems will have simple solutions.
  $endgroup$
  – therealshankman
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dfhwze That's only since someone butchered the title. It originally said finding.
  $endgroup$
  – mdfst13
  5 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?

Your solution requires $O(x)$ time; it should be possible in $O(1)$.

share|improve this answer

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

$endgroup$

share|improve this answer

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

edited 6 hours ago

dfhwze

5,25511 gold badge77 silver badges3636 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

answered 11 hours ago

200_success200_success

135k2121 gold badges172172 silver badges441441 bronze badges

0

$begingroup$

If I were to compute the answer, I'd do (language shown is JavaScript):

var n = 1e8;
var v = Math.floor(n / 3);

6 has two multiples of three less than or equal to it: 6 / 3 == 2
127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.

Likewise, 3 * n will have n multiples of three, including three itself.

share|improve this answer

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm using Java here. Doing long/int division in Java ignores the decimal section anyways. But thanks for the answer, I'll keep it in mind for a later use.
  $endgroup$
  – therealshankman
  13 mins ago
  

  
  
  
  

add a comment | 

0

$begingroup$

If I were to compute the answer, I'd do (language shown is JavaScript):

var n = 1e8;
var v = Math.floor(n / 3);

6 has two multiples of three less than or equal to it: 6 / 3 == 2
127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.

Likewise, 3 * n will have n multiples of three, including three itself.

share|improve this answer

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm using Java here. Doing long/int division in Java ignores the decimal section anyways. But thanks for the answer, I'll keep it in mind for a later use.
  $endgroup$
  – therealshankman
  13 mins ago
  

  
  
  
  

add a comment | 

$begingroup$

If I were to compute the answer, I'd do (language shown is JavaScript):

var n = 1e8;
var v = Math.floor(n / 3);

6 has two multiples of three less than or equal to it: 6 / 3 == 2
127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.

Likewise, 3 * n will have n multiples of three, including three itself.

share|improve this answer

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

var n = 1e8;
var v = Math.floor(n / 3);

share|improve this answer

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1

New contributor

VisualPlugin Rōblox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 41 mins ago

VisualPlugin RōbloxVisualPlugin Rōblox

1