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
1Sample Output 0
1Explanation 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
9Sample Output 1
1Explanation 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.
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()
