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:
- 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.
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("%dn", 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: %dn", 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 != ' ' )
{
exit(EXIT_FAILURE);
}
int result = divisibleNumbers(n);
fprintf(fptr, "%dn", 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] = ' ';
}
if( data[data_length - 1] != ' ' )
{
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = ' ';
}
data = realloc(data, data_length);
return data;
}
