HackerRank Divisible Numbers problem solution YASH PAL, 31 July 2024 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. Topics we are covering Toggle Problem solution in Java.Problem solution in C++.Problem solution in C. 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; } Algorithms coding problems solutions