# 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;

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;

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;
}

++ 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>
int divisibleNumbers(int 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;
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;
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];
{
updated = true;
int hitcheck = rephit[( n - nextmod ) % n];
if( hitcheck >= initlen || dig < hitcheck )
{
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);
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++;
}
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* n_endptr;
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;
}
{
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
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()```
```

## 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

## 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

## 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) =