Spy Number

easy Number Problems

Problem

A spy number has a digit sum that is equal to its digit product. Example: 1124 has sum 1 + 1 + 2 + 4 = 8 and product 1 x 1 x 2 x 4 = 8. Read a positive integer and print true if it is a spy number, otherwise false.

Constraints

  • 1 <= n <= 10^9

Examples

Input

1124

Output

true

Input

12

Output

false

Solutions

Best approachTime O(d)Space O(1)

In one loop we keep two values: the sum and the product of the digits. At the end we compare them. Every single-digit number is a spy number.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Check if a number is a spy number.
 * Input   : One integer.
 * Output  : true or false.
 * Approach: Compare the sum and the product of the digits.
 * Time    : O(d)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives a number and returns true if the number is a spy number.
    static boolean isSpy(long number) {
        // Step 1: Only positive numbers are checked.
        if (number < 1) {
            return false;
        }

        // Step 2: The sum starts at 0 and the product starts at 1 (1 does not change a product).
        long sum = 0;
        long product = 1;
        long remaining = number;

        // Step 3: Repeat until no digits are left.
        while (remaining > 0) {
            // Step 3a: Take the last digit. Example: 1124 % 10 = 4.
            long digit = remaining % 10;

            // Step 3b: Add the digit to the sum and multiply it into the product.
            sum = sum + digit;
            product = product * digit;

            // Step 3c: Remove the last digit. Example: 1124 / 10 = 112.
            remaining = remaining / 10;
        }

        // Step 4: The number is a spy number if the sum equals the product.
        return sum == product;
    }

    public static void main(String[] args) {
        long number = new Scanner(System.in).nextLong();
        System.out.println(isSpy(number));
    }
}
Hints (2)
  1. Which operator gives the last digit?
  2. Which operation removes the last digit?