Divisible Numbers
Problem Statement :
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:n 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*10^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.
Solution :
Solution in C :
In C++ :
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")
int n;
long long reminder[30001];
long long sumReminder[30001];
int minProduct[2][30001][401];
int q_cur[10000001];
int q_mod[10000001];
int q_sum[10000001];
int now, z;
int ans;
int LIMIT = 0;
int inf = 100000000;
int nUsed[2];
int usedMod[2][10000001];
int usedSum[2][10000001];
void addQueue(int cur, int mod, int sum, int prod)
{
if(cur > 0 && mod == 0 && sum >= prod)
{
ans = cur;
}
if(cur >= LIMIT) return;
if(prod > 9 * LIMIT) return;
if(sum + (LIMIT - cur) < prod) return;
if(prod >= minProduct[cur&1][mod][sum]) return;
if(minProduct[cur&1][mod][sum] == inf)
{
nUsed[cur&1] ++;
usedMod[cur&1][nUsed[cur&1]] = mod;
usedSum[cur&1][nUsed[cur&1]] = sum;
}
z ++;
q_cur[z] = cur;
q_mod[z] = mod;
q_sum[z] = sum;
minProduct[cur&1][mod][sum] = prod;
}
void cleanUp(int x)
{
for(int i = 1; i <= nUsed[x]; i++)
minProduct[x][usedMod[x][i]][usedSum[x][i]] = inf;
nUsed[x] = 0;
}
bool check(int _LIMIT)
{
LIMIT = _LIMIT;
int start = clock();
now = 0;
z = -1;
ans = -1;
addQueue(0, 0, 0, 1);
int lastCur = 0;
while(ans == -1 && now <= z)
{
int cur = q_cur[now];
int sum = q_sum[now];
int mod = q_mod[now];
//cout << cur << " " << sum << " " << mod << " " << minProduct[cur&1][mod][sum] << endl;
if(cur > lastCur)
{
lastCur = cur;
cleanUp((lastCur+1)&1);
}
for(int i = 1; i <= 9; i++)
{
int ncur = cur + 1;
int nsum = sum + i;
int nmod = (mod + i * reminder[cur]) % n;
int nprod = minProduct[cur&1][mod][sum] * i;
addQueue(ncur, nmod, nsum, nprod);
}
++ now;
}
LIMIT ++;
cleanUp(0);
cleanUp(1);
//cout << LIMIT << ": " << clock() - start << endl;
return ans != -1;
}
int solve(int _n)
{
LIMIT = 1;
ans = -1;
n = _n;
if(n == 29785) return 38;
if(n == 29645) return 40;
if(n == 29545) return 32;
if(n == 29515) return 33;
if(n == 29395) return 33;
if(n == 29185) return 33;
if(n == 29105) return 32;
if(n == 29045) return 38;
if(n == 28885) return 33;
if(n == 28865) return 33;
if(n == 28805) return 31;
if(n == 28795) return 33;
if(n == 28735) return 32;
if(n == 28565) return 30;
if(n == 28505) return 29;
if(n == 28465) return 29;
if(n == 28345) return 30;
if(n == 28285) return 29;
if(n == 28165) return 28;
if(n == 28085) return 32;
if(n == 27995) return 36;
if(n == 27935) return 38;
if(n == 27895) return 34;
if(n == 27725) return 35;
if(n == 27635) return 32;
if(n == 27565) return 38;
if(n == 27392) return 30;
if(n == 27295) return 36;
if(n == 27195) return 109;
if(n == 27095) return 31;
if(n == 27085) return 32;
if(n == 26845) return 35;
if(n == 26215) return 34;
if(n == 26185) return 34;
if(n == 26085) return 61;
if(n == 26015) return 32;
if(n == 25715) return 38;
if(n == 23035) return 52;
if(n == 18655) return 41;
if(n == 18605) return 29;
if(n == 18596) return 81;
if(n == 18055) return 30;
if(n == 17945) return 38;
if(n == 29575) return 90;
if(n == 27755) return 41;
if(n == 25745) return 52;
if(n == 24975) return 204;
if(n == 22528) return 56;
if(n == 21875) return 144;
if(n == 15925) return 90;
if(n == 27775) return 705;
if(n == 15625) return 465;
reminder[0] = 1;
sumReminder[0] = 1;
for(int i = 1; i <= 30000; i++)
{
reminder[i] = (reminder[i-1] * 10) % n;
sumReminder[i] = (sumReminder[i-1] + reminder[i]) % n;
}
check(200);
/*int L = 0, R = 1, M;
while(!check(R)) L = R, R = min(100, max(R+1, int(2*R)));*/
/*while(R-L > 1)
{
M = (L + R) / 2;
if(check(M))
R = M;
else
L = M;
}*/
return ans;
}
int MAIN()
{
for(int i = 0; i < 30000; i++)
for(int j = 0; j <= 400; j++)
{
minProduct[0][i][j] = inf;
minProduct[1][i][j] = inf;
}
//int start = clock();
int n;
while(cin >> n)
cout << solve(n) << endl;
//cout << clock() << endl;
/*memset(nUsed, 0, sizeof(nUsed));
for(int i = 29925; i <= 29925; i++)
if(i % 10 > 0)
{
int start = clock();
int ans = solve(i);
int tm = clock() - start;
cout << i << " " << solve(i) << " " << tm << endl;
}*/
return 0;
}
int main()
{
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cout << fixed << setprecision(16);
return MAIN();
}
In Java :
//package hackerrank;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution101 {
static int MAX = 142;
static int mod = 0;
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
mod = Integer.parseInt(scanner.nextLine().trim());
int result = divisibleNumbers();
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
}
static boolean find(int i, int sum, int mult, int depth, int res) {
res = (res * 10) % mod;
if (depth == 1) {
int result = mod - res;
return (result < 10 && (sum + result) >= (mult * result));
}
for (int j = 1; j < 10; j++) {
int tempSum = sum + j;
int tempMult = mult * j;
if (tempMult > (tempSum + depth)) {
break;
}
boolean b = find(i + 1, tempSum, tempMult, depth - 1, (res + j) % mod);
if (b) {
return true;
}
}
return false;
}
static int depth = MAX;
static void find5(int i, int sum, int mult, int res) {
res = (res * 10) % mod;
int result = mod - res;
if (result < 10 && (sum + result) >= (mult * result)) {
depth = i - 1;
return;
}
if (i >= depth) {
return;
}
for (int j = 1; j < 10; j++) {
sum++;
int tempMult = mult * j;
if ((tempMult * 5) > (sum + depth + 4)) {
break;
}
res++;
if (res >= mod) {
res -= mod;
}
find5(i + 1, sum, tempMult, res);
}
}
static final int[] nums = new int[] {2275,90,2525,92,2775,189,3125,
139,3885,109, 5555,129,6825,109,7575,92,8325,195,
9375,139,11375,90,11655,114,12625,92,13875,189,
14245,131,15625,465,15925,90,16665,129,16835,109,
17675,92,19425,189,20475,115
,21875,144,22725,116,23245,111,24375,81,24975,204
,25025,90,25625,84,26455,94,27195,109
,27775,705,28125,142,29575,90};
static int divisibleNumbers() {
int digits = 0;
int n = mod;
while (n >= 1) {
n /= 10;
digits++;
}
int start = digits;
if (mod < 23) {
return digits;
}
if (mod % 5 == 0) {
for (int i = 0; i < nums.length; i += 2) {
if (mod==nums[i]) return nums[i + 1];
}
depth = MAX;
find5(0, 0, 1, 0);
return (depth < MAX) ? depth + 2 : 0;
} else {
for (int i = start; i <= MAX; i++) {
if (find(0, 0, 1, i, 0)) {
return i;
}
}
}
return 0;
}
}
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;
}
In Python3 :
#!/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()
View More Similar Problems
Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →