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
Queue using Two Stacks
A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed. A basic que
View Solution →Castle on the Grid
You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):
View Solution →Down to Zero II
You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.
View Solution →Truck Tour
Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr
View Solution →Queries with Fixed Length
Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon
View Solution →QHEAP1
This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element
View Solution →
