How to solve "Zero-One" multiple coding Solution?

Question

Given a number N, find the smallest "zero-one" number S that is a multiple of N. A "zero-one" number consists of the digits 0 and/or 1.

E.g. If N=4 then S=100 Here 100 is smallest integral multiple of 4 whose representation consist of only 0and/or 1 digits.

I tried doing it in a brute-force way, but I'm looking for an efficient solution.

Answer 1

You need to search for the smallest number to multiply N by.

I would construct the number incrementally, starting from the least significant digit.

Supposing N=7. What are the possible least significant digits of the multiplying number? It will be a number which, when you multiply by 7, will have a result with the least significant digit of 0 or 1. If you try the numbers from 0-9, it can only be '0' or 3'.

+-------+--------+------+
| Digit | Result | Pass |
+-------+--------+------+
| 0     |  0     | Yes  |
| 1     |  7     | No   |
| 2     | 14     | No   |
| 3     | 21     | Yes  |
| 4     | 28     | No   |
| 5     | 35     | No   |
| 6     | 42     | No   |
| 7     | 49     | No   |
| 8     | 56     | No   |
| 9     | 63     | No   |
*-------*--------*------*

Then you try the second least significant digit. You will now try 00, 10, 20, 30, 40, 50, 60, 70, 80, 90 and 03,13,23,43,53,63,73,83,93. The successful candidates will be the ones when, multiplied by 7, produce a number in which the two least significant digits are 0 or 1. You are left with '43', '30', '00', and '01'.

Repeat this process with the 3rd digit, finding the number which produces a multiple with 3 least significant digits meeting the qualities.

During the process you will find a number in which ALL of the digits meet the qualities, and that's your answer. In the case of N=7, you've found it by the 3rd digit. (7 * 143 == 1001).

Answer 2

Here is an alternative approach using BFS.

Starting with a root node with value 1, you build a decision tree of whether to append a 0 or 1. Each node hence represents a number using digits 0s and 1s. You then perform BFS to find the lowest such number which is also a multiple of the input number.

This solution also leverages modulo (of the input number) to compute really large results. Full description available in the comments in the code.

You can also access the same code snippet in ideone.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    // Return the smallest multiple of the number (as a string) consisting only of digits 0 and 1
    //
    // All possible digits that can be constructed using the digits 0/1 can be represented
    // as a tree, where at each level, appending a 0 is one branch and appending a 1 is another
    //
    // If we perform BFS on this tree, the first number we see which is an exact multiple of the input
    // number will be the result (since it will be the smallest). Make sure to consider left
    // branch (i.e. 0) before considering the right branch (i.e. 1)
    //
    // The 2 paths we take at each level when the current number is num:
    //      (num * 10)
    //      (num * 10) + 1
    // 
    // Since the result can grow huge quite easily, it might not be possible to store the result in a
    // 32 or even a 64 bit int/long variable.
    //
    // One alternative is to use BigNumber, but a simpler alternative exists if we leverage modulo.
    //
    // The operations we perform above (i.e. multiplications and additions) will retain the useful part
    // of the result when using modulo. We use the given number itself as the modulo, and when we see a
    // result of 0, it means we have found a number which is an exact multiple of the input number.
    //
    // To reconstruct the number, we need to store the parent nodes of each node, when adding the node
    // in the queue (similar to using BFS for computing shortest path)
    //
    // We will also need to know if we appended a 0 or a 1 at each step, and so we add this information
    // as part of the node data structure as well.
    //
    // Re-visiting nodes is unecessary since we have seen this modulo result (i.e. value % num) already.
    // Any additional digits we add from now will only make the number longer and we already are tracking
    // the path for this same modulo result we've seen earlier.
    //
    public static String multiple(int num) {
        if (num < 0) {
            throw new IllegalArgumentException("Invalid args");
        }

        String result = "0";

        if (num > 0) {
            // An array to mark all the visited nodes
            boolean[] isVisited = new boolean[num];
            Arrays.fill(isVisited, false);

            // The queue used by BFS
            Queue<Node> queue = new ArrayDeque<>();

            // Add the first number 1 and mark it visited
            queue.add(new Node(true, 1 % num, null));
            isVisited[1 % num] = true;

            // The final destination node which represents the answer
            Node destNode = null;

            while (!queue.isEmpty()) {
                // Get the next node from the queue
                Node currNode = queue.remove();

                if (currNode.val == 0) {
                    // We have reached a valid multiple of num
                    destNode = currNode;
                    break;
                } else {
                    // Visit the next 2 neighbors
                    // Append 0 - (currNode.val * 10)
                    // Append 1 - (currNode.val * 10) + 1

                    // Append a '0'
                    int val1 = (currNode.val * 10) % num;
                    if (!isVisited[val1]) {
                        queue.add(new Node(false, val1, currNode));
                        isVisited[val1] = true;
                    }

                    // Append a '1'
                    int val2 = (val1 + 1) % num;
                    if (!isVisited[val2]) {
                        queue.add(new Node(true, val2, currNode));
                        isVisited[val2] = true;
                    }
                }
            }

            // Trace the path from destination to source
            if (destNode == null) {
                throw new IllegalStateException("Result should not be null");
            } else {
                StringBuilder reverseResultBuilder = new StringBuilder();
                Node currNode = destNode;
                while (currNode != null) {
                    reverseResultBuilder.append(currNode.isDigitOne ? '1' : '0');
                    currNode = currNode.parent;
                }
                result = reverseResultBuilder.reverse().toString();
            }
        }

        return result;
    }

    // Node represents every digit being appended in the decision tree
    private static class Node {
        // True if '1', false otherwise (i.e. '0')
        public final boolean isDigitOne;
        // The number represented in the tree modulo the input number
        public final int val;
        // The parent node in the tree
        public final Node parent;

        public Node(boolean isDigitOne, int val, Node parent) {
            this.isDigitOne = isDigitOne;
            this.val = val;
            this.parent = parent;
        }
    }

    public static void main(String[] args) {
        int num = new Scanner(System.in).nextInt();
        System.out.println("Input number: " + num);
        System.out.println("Smallest multiple using only 0s and 1s as digits: " + Main.multiple(num));
    }
}

Answer 3

How about this: you try a series of numbers :1, 10, 100, 1000, 10000,..... and you divide each number by N and you record the remainder E.g. N = 9, 1/9 = 1 10 = 1(mod 9), 100 = 1(mod 9), .... The point is that you need to choose specific number from this series and make sure that these remainder add up to multiples times of N. E.g. N = 9, then you add 1, 10, 100, ....

I would suggest to use the algorithm: Once the sum of remainder of the series > N, try to search in remainder for remainders that sum up to N etc

Answer 4

Iterate over a for loop ,convert the input number into binary,then convert the binary number to long and check whether the number is divisible by the input number.

here is the code:

private Long getno(int n) {

        for(int i=1;;i++)
        {
            String binary=Integer.toBinaryString(i);

            Long no=Long.parseLong(binary);

            if(no%n==0)
            {
                return no;
            }
        }


    }