CF 102697028 - Funny Numbers

CF 102697028 - Funny Numbers

Rating: -
Tags: -
Solve time: 1m 41s
Verified: yes

Solution

Problem Understanding

The problem asks us to decide whether a given positive integer is a "funny number". A number receives this label only when it can be divided evenly by both 5 and 7. The input contains one integer, and the output should be YES if the condition is satisfied and NO otherwise.

The only operation we need is checking divisibility. Since the number is tested against two fixed values, the algorithm does not depend on the size of the input number except for reading it. Even if the value is very large, a constant number of arithmetic operations is enough. A solution that tries to search through multiples or repeatedly subtract values would add unnecessary work and could be much slower than a direct divisibility check.

The main edge cases come from forgetting that both conditions are required. A number divisible by 5 alone is not enough. For example:

Input:

25

The correct output is:

NO

because 25 is divisible by 5 but not by 7. A careless solution checking only one divisor would incorrectly print YES.

Another case is a number divisible by 7 but not 5.

Input:

14

The correct output is:

NO

because 14 satisfies only one half of the requirement.

The smallest valid case is the least common multiple of 5 and 7.

Input:

35

The correct output is:

YES

because 35 is divisible by both numbers.

Approaches

The straightforward brute-force idea is to repeatedly test whether the number can be reduced by subtracting 5 or 7 until reaching zero. This would eventually reveal whether the number is a multiple of either value, but it is the wrong model for this problem. For a large input value, this can require many unnecessary iterations, and it still does not naturally combine the two divisibility conditions.

The key observation is that divisibility is already provided by the remainder operation. A number x is divisible by another number y exactly when x % y equals zero. Since the problem asks for divisibility by two fixed values, we only need two remainder checks.

The brute-force method works because it tries to discover whether the number belongs to the set of multiples of a divisor. The observation that the remainder directly answers membership in that set reduces the entire problem to constant time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n)	O(1)	Too slow for unnecessarily large values
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Read the given number from input. The number is the only piece of information needed, because the condition depends only on its divisibility.
2. Check whether the number leaves remainder zero when divided by 5 and when divided by 7. Both checks must succeed because the definition requires both properties at the same time.
3. Print YES if both remainders are zero. Otherwise print NO.

Why it works

The invariant behind the algorithm is simple: after each divisibility check, we know whether the input belongs to the multiples of that divisor. A number is funny exactly when it belongs to the multiples of both 5 and 7, so the final condition matches the definition directly. There is no missing case because every integer either has remainder zero or a nonzero remainder when divided by each divisor.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    if n % 5 == 0 and n % 7 == 0:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    solve()

The solution reads the single integer and applies two modulo operations. The expression n % 5 == 0 checks whether 5 divides the number exactly, while n % 7 == 0 performs the same check for 7. The logical and is necessary because a number satisfying only one condition is not funny.

There are no overflow concerns in Python because integer arithmetic handles large values automatically. The condition order also does not create boundary problems because both divisors are constant and every positive integer is handled by the same two checks.

Worked Examples

For the first sample:

Input:

21

Number	Divisible by 5	Divisible by 7	Output
21	No	Yes	NO

The trace shows that satisfying one divisor is insufficient. The algorithm rejects the number because both conditions are not true.

For the second sample:

Input:

35

Number	Divisible by 5	Divisible by 7	Output
35	Yes	Yes	YES

This confirms the valid case. The number passes both checks, so the algorithm accepts it.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only two modulo operations are performed
Space	O(1)	Only the input number is stored

The solution uses a fixed amount of work regardless of the value of the input number, so it easily fits within the given limits.

Test Cases

import sys
import io

def solve(inp: str) -> str:
    old_stdin = sys.stdin
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    n = int(input())
    ans = "YES" if n % 5 == 0 and n % 7 == 0 else "NO"

    sys.stdin = old_stdin
    return ans + "\n"

assert solve("21\n") == "NO\n", "sample 1"
assert solve("35\n") == "YES\n", "sample 2"

assert solve("1\n") == "NO\n", "minimum value"
assert solve("1000000000\n") == "NO\n", "large boundary value"
assert solve("70\n") == "YES\n", "multiple of both divisors"
assert solve("25\n") == "NO\n", "divisible by only one divisor"

Test input	Expected output	What it validates
1	NO	Smallest possible input
1000000000	NO	Large value handling
70	YES	A valid multiple of both divisors
25	NO	Rejecting numbers divisible by only one divisor

Edge Cases

A number divisible by 5 but not 7 must be rejected. For input 25, the algorithm computes 25 % 5 = 0 and 25 % 7 = 4, so the second condition fails and the output is NO.

A number divisible by 7 but not 5 must also be rejected. For input 14, the algorithm finds 14 % 5 = 4 and 14 % 7 = 0, so the first condition fails and the output is NO.

The first valid number is 35. For input 35, both remainders are zero, so the algorithm reaches the accepting branch and prints YES.

I can also provide a shorter contest-style editorial version if you want something closer to what would appear in an official Codeforces tutorial.