In this HackerRank Divisible Numbers problem solution we have Given an integer, N, find the smallest integer M such that M is divisible by  N(i.e., N is a factor of M) and satisfies the following properties:

  1. M must not contain zeroes in its decimal representation.
  2. The sum of M's digits must be greater than or equal to the product of M's digits.

Given N, find M and print the number of digits in M's decimal representation.

HackerRank Divisible Numbers problem solution


Problem solution in Java.

import java.io.*;
import java.util.*;

import java.math.BigInteger;

public class SolutionDiv2 {


    private static Map<Integer, String> ones = new HashMap<>();

    private static void swap(StringBuilder s, int i, int j) {
        char t = s.charAt(i);
        s.setCharAt(i, s.charAt(j));
        s.setCharAt(j, t);
    }

    private static void rev(StringBuilder s, int l, int r) {
        while (l < r)
            swap(s, l++, r--);
    }

    private static int bsearch(StringBuilder s, int l, int r, int key) {
        int index = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (s.charAt(mid) <= key)
                r = mid - 1;
            else {
                l = mid + 1;
                if (index == -1 || s.charAt(index) >= s.charAt(mid))
                    index = mid;
            }
        }
        return index;
    }

    static boolean nextPermutation(StringBuilder s, int threshold) {

        int len = s.length(), i = len - 2;
        while (i >= threshold && s.charAt(i) >= s.charAt(i + 1))
            --i;
        if (i < threshold)
            return false;
        else {
            int index = bsearch(s, i + 1, len - 1, s.charAt(i));
            swap(s, i, index);
            rev(s, i + 1, len - 1);
            return true;
        }
    }

    static List<String> getCombinations(int length, String suffix, int lastDigit, int sum, int product, int threshold, int modifiedCount) {
        List<String> temp = new ArrayList<>();
        if (suffix.length() == length) {
            temp.add(suffix);
            return temp;
        } else if (modifiedCount == threshold) {
            temp.add(ones.get(length - threshold) + suffix);
            return temp;
        }
        for (int i = 1; i <= lastDigit; i++) {
            if (length - modifiedCount + sum + i > product * i) {
                temp.addAll(getCombinations(length, i + suffix, i, sum + i, product * i, threshold, modifiedCount + 1));
            }
        }
        return temp;
    }

    private static int sum(String s) {
        int sum = 0;
        for (int d : s.toCharArray()) {
            sum += (d - 48);
        }
        return sum;
    }

    private static boolean contains(String s, int d) {
        d += 48;
        int i = s.length() - 1;
        while (i >= 0) {
            if (s.charAt(i) == d) return true;
            else if (s.charAt(i) < d) return false;
            i--;
        }
        return false;
    }

    public static void main(String[] args) {
        StringBuilder temp = new StringBuilder("");
        for(int ii = 0; ii < 800; ii++) {
            ones.put(ii, temp.toString());
            temp.append("1");
        }
        Scanner in = new Scanner(System.in);
        BigInteger nb = in.nextBigInteger();
        Integer n = nb.intValue();
        boolean checkTwo = n % 2 == 0;
        boolean checkThree = n % 3 == 0;
        boolean checkFive = n % 5 == 0;
        boolean check25 = n % 25 == 0;
        int threshold = 0;
        for (int i = 1; i < 1000; i++) {
            
            if (i > 470 && i < 705) i = 705;
            if (i > 190) threshold = i - 7;
            else if (i > 150) threshold = i - 8;
            else if (i > 120) threshold = i - 10;
            else if (i > 90) threshold = i - 12;
            else if (i > 62) threshold = i - 15;
            else if (i > 40) threshold = i - 19;
            else if (i > 30) threshold = i / 2;
            for (String s : getCombinations(i, "", 9, 0, 1, i - threshold, 0)) {
                
                if (checkTwo) {
                    
                    if (!contains(s, 2) && contains(s, 4) && contains(s, 6) && contains(s, 8)) continue;
                } else if (checkFive) {
                    if (!contains(s, 5)) continue;
                    
                    if (check25 && !(contains(s, 2) || (contains(s, 7) && (contains(s, 3) || contains(s, 8))))) continue;
                }
                if (checkThree) {
                    if (sum(s) % 3 != 0) continue;
                }
                StringBuilder t = new StringBuilder(s);
                do {
                    
                    if (checkTwo) {
                        if (t.charAt(i - 1) % 2 == 1 ) continue;
                    } else if (checkFive) {
                        if (t.charAt(i - 1) != 53) continue;
                        if (check25 && i > 5) {
                            if (!(t.charAt(i - 2) == 50 && (t.charAt(i - 3) == 49 || t.charAt(i - 3) == 54)) &&
                                    !(t.charAt(i - 2) == 55 && (t.charAt(i - 3) == 51 || t.charAt(i - 3) == 56)))
                                continue;
                        }
                    }
                    if (new BigInteger(t.toString()).mod(nb).equals(BigInteger.ZERO)) {
                        System.out.println(t.length());
                        return;
                    }
                } while (nextPermutation(t, threshold));
            }
        }
    }
}


Problem solution in C++.

#include <iostream>
#include <cstdio>
#include <vector>
    
using namespace std;
    
bool add(int value, vector < int >* digits) {
    digits->at(0) += value;
    for (int i = 0; i + 1 < digits->size(); ++i) {
        if (digits->at(i) >= 10) {
            digits->at(i + 1) += digits->at(i) / 10;
            digits->at(i) %= 10;
        } 
        else {
            break;
        }
    }
    return digits->back() < 10;
}
    
int getSum(const vector < int >& digits) {
    int res = 0;
    const int significant_digits = min((int)digits.size(), 30);
    for (int i = 0; i < significant_digits; ++i) {
        res += digits[i];
    }
    res += digits.size() - significant_digits;
    return res;
}
    
int getProduct(const vector < int >& digits) {
    int res = 1;
    const int significant_digits = min((int)digits.size(), 30);
    const int inf = 1000000;
    for (int i = 0; i < significant_digits; ++i) {
        res *= digits[i];
        if (res > inf) {
            res = inf;
            break;
        }
    }
    return res;
}
    
int largest = 0;
    
bool build(int n, int length, vector < int >* digits) {
    int rem = 0;
    for (int i = length - 1; i >= 0; --i) {
        rem = rem * 10 + digits->at(i);
        rem %= n;
    }
    if (!add((n - rem) % n, digits)) {
        return false;
    }
    int iterations = 0;
    const int max_iterations = n;

    while (iterations < max_iterations) {
        ++iterations;
        int sum = getSum(*digits);
        int product = getProduct(*digits);
        if (product == 0 || sum < product) {
            if (!add(n, digits)) {
                return false;
            }
            continue;
        }
        return true;
    }
    
    return false;
}

bool try_to_build(int n, int length) {
    vector < int > digits(length, 1);
    if (build(n, length, &digits)) {
        return true;
    }
    return false;
}

int solve(int n) {
    if (n % 10 == 0) {
        return -1;
    }
    int starting_length = 60;
    
    for (int length = starting_length; ; ++length) {
        if (try_to_build(n, length)) {
            return length;
        }
    }
}

const int maxS = 75;
const int maxN = 30000;
unsigned char d[maxS][maxS][maxN];

int clever(int n) {
    if (n % 10 == 0) {
        return -1;
    }
    const int inf = 250;
    for (int i = 0; i < maxS; ++i) {
        for (int j = 0; j < maxS; ++j) {
            for (int k = 0; k < maxN; ++k) {
                d[i][j][k] = inf;
            }
        }
    }
    d[0][1][0] = 0;
    for (int i = 0; i < maxS; ++i) {
        for (int j = 0; j < maxS; ++j) {
            for (int k = 0; k < n; ++k) {
                if (d[i][j][k] == inf) {
                    continue;
                }
    
                for (int digit = 1; digit < 10; ++digit) {
                    if (i + digit < maxS && j * digit < maxS) {
                        int l = (k * 10 + digit) % n;
                        d[i + digit][j * digit][l] = min(
                            d[i + digit][j * digit][l], 
                            (unsigned char)(d[i][j][k] + 1)
                        );
                    }
                }
            }
        }
    }
    
    int res = 1000000;
    for (int i = 1; i < maxS; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (d[i][j][0] != inf) {
                res = min(res, (int)(d[i][j][0]));
            }
        }
    }
    return res;
}
    
int main() {
    int n;
    scanf("%d", &n);
    int res = clever(n);
    if (res == 1000000) {
        res = solve(n);
    }
    printf("%d\n", res);
    return 0;
}


Problem solution in C.

#include<assert.h>
#include<limits.h>
#include<math.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXADD 20
char* readline();
int divisibleNumbers(int n)
{
    int pow10[n*MAXADD + 1], rep1mod[n*MAXADD + 1], rephit[n];
    for( int i = 0 ; i < n ; i++ )
    {
        rephit[i] = -1;
    }
    pow10[0] = 1;
    rep1mod[0] = 0;
    rephit[0] = 0;
    int initlen = -1, period = -1;
    for( int i = 0 ; i < n * MAXADD ; i++ )
    {
        pow10[i + 1] = ( 10 * pow10[i] ) % n;
        rep1mod[i + 1] = ( 10 * rep1mod[i] + 1 ) % n;
        if( rephit[rep1mod[i + 1]] == -1 )
        {
            rephit[rep1mod[i + 1]] = i + 1;
        }
        else
        {
            if( initlen == -1 )
            {
                initlen = rephit[rep1mod[i + 1]];
                period = i + 1 - initlen;
            }
        }
    }
    int dig = 0;
    int lowprod[MAXADD][n];
    for( int i = 0 ; i < MAXADD ; i++ )
    {
        for( int j = 0 ; j < n ; j++ )
        {
            lowprod[i][j] = INT_MAX / 10;
        }
    }
    lowprod[0][0] = 1;
    int lastupdate = 0, toreturn = ( initlen == 0 ? period : INT_MAX );
    while( dig < toreturn )
    {
        bool updated = false;
        int nextlowprod[MAXADD][n];
        for( int i = 0 ; i < MAXADD ; i++ )
        {
            for( int j = 0 ; j < n ; j++ )
            {
                nextlowprod[i][j] = lowprod[i][j];
            }
        }
        for( int i = 0 ; i < MAXADD ; i++ )
        {
            for( int thedig = 2 ; thedig < 10 && thedig + i <= MAXADD ; thedig++ )
            {
                int nextadd = thedig + i - 1;
                for( int j = 0 ; j < n ; j++ )
                {
                    int nextmod = ( j + ( thedig - 1 ) * pow10[dig] ) % n;
                    int prodcheck = thedig * lowprod[i][j];
                    if( prodcheck < nextlowprod[nextadd][nextmod] )
                    {
                        nextlowprod[nextadd][nextmod] = prodcheck;
                        updated = true;
                        int hitcheck = rephit[( n - nextmod ) % n];
                        if( hitcheck >= initlen || dig < hitcheck )
                        {
                            int extra = nextlowprod[nextadd][nextmod] - nextadd;
                            if( extra <= hitcheck )
                            {
                                extra = hitcheck;
                            }
                            else
                            {
                                if( hitcheck >= initlen )
                                {
                                    extra = ( ( extra - hitcheck - 1 ) / period + 1 ) * period + hitcheck;
                                }
                                else
                                {
                                    continue;
                                }
                            }
                            if( dig < extra && extra < toreturn )
                            {
                                printf("Updating tr to %d based on (%d, %d, %d, %d); hc: %d\n", extra, nextadd, nextmod, nextlowprod[nextadd][nextmod], dig,  hitcheck);
                                toreturn = extra;
                            }
                        }
                    }
                }
            }
        }
        for( int i = 0 ; i < MAXADD ; i++ )
        {
            for( int j = 0 ; j < n ; j++ )
            {
                lowprod[i][j] = nextlowprod[i][j];
            }
        }
        if( updated == false )
        {
            break;
        }
        dig++;
    }
    return toreturn;
}
int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);
    if( n_endptr == n_str || *n_endptr != '\0' )
    {
        exit(EXIT_FAILURE);
    }
    int result = divisibleNumbers(n);
    fprintf(fptr, "%d\n", result);
    fclose(fptr);
    return 0;
}
char* readline()
{
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);
    while(true)
    {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);
        if(!line)
        {
            break;
        }
        data_length += strlen(cursor);
        if( data_length < alloc_length - 1 || data[data_length - 1] == '\n' )
        {
            break;
        }
        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);
        if(!data)
        {
            break;
        }
        alloc_length = new_length;
    }
    if( data[data_length - 1] == '\n' )
    {
        data[data_length - 1] = '\0';
    }
    if( data[data_length - 1] != '\0' )
    {
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '\0';
    }
    data = realloc(data, data_length);
    return data;
}