A number, $x$, is said to be a multiple of another number, $y$, if the remainder of $x/y$ is $0$. Similarly, a number, $n$, will be a multiple of 3 and 5 if the remainder of $n/3$ and $n/5$ is equal to $0$.

In order to find all the numbers from $0$ to $N$ that are multiples of 3 and 5, each number needs to be considered separately, and the remainders of both $n/3$ and $n/5$ should be compared to $0$.

Since the range $0$ to $N$ is traversed only once, the time complexity of this algorithm is $O(n)$.

The following code implements this algorithm in C++, Java, and Python:

#include <iostream>using namespace std;void findMultiples(int n){for(int i = 0; i <= n; i++)if(i % 3 == 0 && i % 5 == 0)cout << i << endl;}int main() {findMultiples(120);return 0;}

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS