HackerRank Divisible Numbers Problem Solution

In this post, we will solve HackerRank Divisible Numbers Problem Solution.

Given an integer, n. find the smallest integer m such that m is divisible by n (ie., n is a factor of m) and satisfies the following properties:
m must not contain zeroes in its decimal representation.

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.
Input Format
A single integer denoting n.
Constraints
1 ≤ n ≤ 3 x 10 power 4
n is not divisible by 10.
Time Limits
The time limits for this challenge are available here.
Output Format
Print the number of digits in the decimal representation of the smallest possible m.

Sample Input 0

Sample Output 0

Explanation 0
m = 1 is evenly divided by n = 1. doesn’t contain any zeroes in its decimal representation, and the sum of its digits is not less than the product of its digits. Thus, we print the number of digits in m = 1 (which also happens to be 1) as our answer.

Sample Input 1

Sample Output 1

Explanation 1
m = 9 is evenly divided by n = 9, doesn’t contain any zeroes in its decimal representation, and the sum of its digits is not less than the product of its digits. Thus, we print the number of digits in m = 9, which is 1, as our answer.

HackerRank Divisible Numbers Problem Solution

Divisible Numbers C Solution

#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;
}

Divisible Numbers C++ Solution

#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;
}

Divisible Numbers C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;

class Solution {

    /*
     * Complete the divisibleNumbers function below.
     */

        public struct Details {

            public int sum { get; set; }
            public int product { get; set; }
            public bool isNumber { get; set; }
        }


        static int divisibleNumbers(int divisor)
        {

            // for length l mod[n] = (n * 10^l) mod divisor
            var mod = new int[10];

            for (int i = 1; i < 10; i++)
            {
                mod[i] = i % divisor;
            }


            

            var result = new Details[][] {
                new Details[divisor],
                new Details[divisor]
            };

            var maxM = int.MinValue;


            var current = 0;
            var length = 1;

            for (int i = 1; i < 10; i++)
            {
                maxM = Math.Max(maxM, mod[i]);


                result[current][mod[i]] = Select(
                    result[current][mod[i]],
                    new Details { sum = i, product = i, isNumber = true });

            }


            while (!IsValid(result[current][0]))
            {
                current ^= 1;
                length++;

                for (int i = 1; i < 10; i++)
                {
                    mod[i] = mod[i] * (10 % divisor) % divisor;
                }

                int maxMCopy = maxM;

                maxM = int.MinValue;

                for (int m = 0; m <= maxMCopy; m++)
                {
                    var prev = result[current ^ 1][m];

                    if (prev.isNumber)
                    {
                        result[current ^ 1][m].isNumber = false;

                        for (int n = 1; n < 10; n++)
                        {
                            var nextM = (m + mod[n]) % divisor;

                            maxM = Math.Max(nextM, maxM);

                            if (!result[current][nextM].isNumber) {
                                result[current][nextM] = 
                                    new Details { 
                                        sum = prev.sum + n, 
                                        product = prev.product * n, 
                                        isNumber = true 
                                    };
                            }
                            else {
                                result[current][nextM] = Select(
                                        result[current][nextM],
                                        new Details { 
                                            sum = prev.sum + n, 
                                            product = prev.product * n, 
                                            isNumber = true 
                                        });
                            }

  
                        }
                    }
                }

                

            }

            return length;

        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static bool IsValid(Details v)
        {
            return v.isNumber && v.sum >= v.product;
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static Details Select(Details n1, Details n2)
        {
            return n1.sum < n1.product && n2.sum < n2.product
                ?  (n1.product - n1.sum < n2.product - n2.sum ? n1 : n2)
                :  (n1.sum * n2.product > n2.sum * n1.product ? n1 : n2);
            
        }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine());

        int result = divisibleNumbers(n);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Divisible Numbers Java Solution

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));
            }
        }
    }
}

Divisible Numbers Python Solution

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from __future__ import absolute_import, division, print_function

from sys import version_info
if version_info.major == 3:
    pass
elif version_info.major == 2:
    input = raw_input
else:
    print ("Unknown python version - input function not safe")
import os
from time import sleep

def getSum (m): 
    sum_ = 0
    while (m != 0): 
        sum_ += m % 10 
        m = m // 10
    return sum_

def getProd (m): 
    if m != 0:
        prod = 1
    else: prod = m
    while (m != 0): 
        prod *= m % 10 
        m = m // 10
    return prod

def getDgtCnt (m): 
    cnt = 0
    while (m != 0): 
        m = m // 10
        cnt += 1
    if cnt == 0: cnt = 1
    return cnt

def createMcBase (first_num, dgtc):
    for i in range (1, dgtc - 1):
        first_num *= 10
    return first_num

def numS (m):
    dgtc = getDgtCnt (m)
    even = False
    def create (first_num):
        for i in range (1, dgtc):
            first_num += 10 ** i
        return first_num
    if m % 10 == 5:
        fstCntDgt = 1
        first_num = 5
        first_num = create (first_num)
    elif m % 2 == 0:
        even = True
        fstCntDgt = 0
        first_num = 2
        first_num = create (first_num)
    else:
        fstCntDgt = 0
        first_num = 1
        first_num = create (first_num)
    cntDgt = fstCntDgt
    numc = num = first_num
    i = 0
    if m == 19425: maxcxv = 8
    elif m % 3885 == 0 or m == 16835 or m == 4095: maxcxv = 7
    else: maxcxv = 6
    maxcv = 19
    maxc = 30
    if m == 26085: maxcx = 61  # braucht 19 Stellen 
    else: maxcx = 41
    up = False
    while True:
        dgt = (num % (10 ** (cntDgt + 1))) // 10 ** cntDgt
        while getSum (num) >= getProd (num) and dgt <= 9:
            if num % m == 0:
                return num
            if cntDgt == 0 and even:
                num += 2
                dgt += 2
            else:
                num += 10 ** cntDgt
                dgt += 1
        """
        while getSum (num) < getProd (num) or dgt > 9:
            Setze Ziffer zurück (beachte even)   *)
            setze Zähler cntDgt (+1) auf nächste Stelle und erhöhe sie
            wenn sie 0 ist erhöhe sie nochmal
            dgt = (num % (10 ** (cntDgt + 1))) // 10 ** cntDgt
        setze Zähler cntDgt zurück auf fstCntDgt
        """
        while getSum (num) < getProd (num) or dgt > 9:
            if cntDgt == 0 and even: num -= (dgt - 2) * 10 ** cntDgt   # *)
            else: num -= (dgt - 1) * 10 ** cntDgt
            cntDgt += 1
            num += 10 ** cntDgt

            dgt = (num % (10 ** (cntDgt + 1))) // 10 ** cntDgt
            numdiff = num - numc

            if dgtc >= maxc and numdiff > 10 ** maxc:
                up = True
                break
            else: up = False
            if dgt == 0:
                num += 10 ** cntDgt
#                print ("0 reset", dgtc, end = ", ")
                dgtp1 = (num % (10 ** (cntDgt + 2))) // 10 ** (cntDgt + 1)
                if dgtp1 == 0:
                    num += 10 ** (cntDgt + 1)
                    print ("00 reset", dgtc, end = ", ")
                    dgtp2 = (num % (10 ** (cntDgt + 3))) // 10 ** (cntDgt + 2)
                    if dgtp2 == 0:
                        num += 10 ** (cntDgt + 2)
                        print ("000 reset", dgtc, end = ", ")
        gtdf = cntDgt + i
        if  gtdf >= dgtc or up: # and not dgtcp1:
            numc += 10 ** dgtc
            dgtc += 1
            if dgtc == maxc + 1: i += maxc - maxcv; maxc = maxcv; # 26085 19 braucht Stellen
            if dgtc == maxcx + 1:  # ab 42 (26085 62) Stellen
                i += maxc - maxcxv
                maxc = maxcxv
                if maxcxv == 6 or m == 19425:
                    break
        if cntDgt >= maxc or up: # or dgtcp1:  # nur bis Stelle maxc durchzählen
            num = numc
            i += 1
        cntDgt = fstCntDgt
    print ("change to algorithm add_m")
    num = (numc // m) * m
    num += m
    if m == 19425:
        overshot = createMcBase (69, maxc)
    else: overshot = createMcBase (49, maxc)
    while True:
        while (getSum (num) < getProd (num) or getProd (num) == 0):
            if getDgtCnt (num - numc + overshot) <= maxc:
                num += m
            else:
                numc += 10 ** dgtc
                dgtc += 1
                num = (numc // m) * m
                num += m
        if num % m == 0:
            return num

def divisibleNumbers (n):
    if getSum (n) >= getProd (n) and getProd (n) != 0:
        return (getDgtCnt (n))
    m = numS (n)
    print (m, getDgtCnt (m))
    return getDgtCnt (m)

def divisibleNumbers_slow (n):
    for m in range (n, 100000000000, n):
        prod = getProd (m)
        if prod == 0:
            pass
        elif getSum (m) >= prod:
            print (m, getDgtCnt (m))
            return (getDgtCnt (m))
    print (m)

# type in bash:
# export OUTPUT_PATH=OUTPUT
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    result = divisibleNumbers(n)

    fptr.write(str(result) + '\n')

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python