Smallest Integer Divisible by K Problem in Java

Problem Statement

Given a positive integer k. We have to find the length of the smallest positive integer named n that is divisible by k and that every digit in n contains only the digit 1. The integer n should be constructed by repeating the digit 1 one or more times. The task is to return the number of digits in the number n. However, if no such number n exists for a given k, we can return -1.

Note: The number n might be so large that it does not fit in a 64-bit signed integer. So, we should focus on the length of the number n rather than constructing the number itself.

Example 1:

Input: k = 7

Output: 6

Explanation: The smallest number consisting only of the digit 1 that is divisible by 7 is 111111. The length of the number 111111 is 6. Therefore, the output is 6.

Example 2:

Input: k = 11

Output: 2

Explanation: The smallest number consisting only of the digit 1 that is divisible by 11 is 11. The length of number 11 is 2.

Example 3:

Input: 5

Output: -1

Explanation: There is no such positive integer n consisting only of the digit 1 that is divisible by 5, because all such numbers end in 1 and are not divisible by 5.

Approach: Using Brute Force

The simplest way to solve this problem is by using the Brute Force approach. The following are the steps to solve the problem.

Step 1: Check if k is divisible by 2 or 5. If yes, return -1.

Step 2: Create a variable named num and initialize the string with 1.

Step 3: Create a variable named length and initialize to 1.

Step 4: While the number represented by num is not divisible by k:

Step 4.1: Append the character 1 to num to create the next repunit.

Step 4.2: Increment length by 1.

Step 5: Check if the length of num exceeds 18 digits. If yes, return -1.

Step 6: Check if the number represented by num is divisible by k using the modulo operation (num % k == 0).

Step 6.1: If it is divisible, exit the loop.

Step 7: Return the smallest length of a sequence of 1’s is divisible by k. Otherwise, return -1 if no such repunit exists.

Output:

 The Smallest integer divisible by 7 is : 6 The Smallest integer divisible by 11 is : 2 The Smallest integer divisible by 5 is : -1 

Complexity Analysis

The time complexity is O(n²), where n is the length of the sequence of 1's because, in each iteration, we append a 1 to the string and perform a divisibility check, which takes O(n) time, and we do this for n iterations.

The space complexity is O(n) because the string num grows in length by one digit per iteration, requiring space proportional to the length of the sequence of 1's.

Approach: Using Greedy

The brute force approach is too slow for large values. Instead of using string operations, we should try using the Greedy approach with mathematical operations that avoid direct number construction. The steps to solve the problem are as follows.

Step 1: Initially, check if k =1. If yes, return 1.

Step 2: Initialize len = 1 to track the length of the smallest valid number.

Step 3: Create a variable named rest to store the remainder of the division.

Step 4: Create the StringBuilder class to store the digits of the number.

Step 5: Iterate Until a Valid Number is Found:

Step 5.1: Set a flag match = false to track if a valid digit is found.

Step 6: Iterate through digits from 0 to 9 to find a valid digit:

Step 6.1: Check if the digit, when multiplied with K and combined with the current remainder, forms a valid repunit pattern.

Step 6.2: If a valid digit is found:

Step 6.2.1: Update rest to store the remainder for the next step.

Step 6.2.2: Append the valid digit to the number.

Step 6.2.3: Set match = true and break the loop.

Step 7: If no valid digit is found in the iteration, return -1.

Step 8: Once a valid number is found, return its length (len).

Output:

 The Smallest integer divisible by 7 is : 6 The Smallest integer divisible by 11 is : 2 The Smallest integer divisible by 5 is : -1 

Complexity Analysis

The program takes O(k) time because, in the worst case, it iterates up to k times. For each iteration, an inner loop runs at most 10 times by taking O(1) time. It also takes o(1) time to check digits and update the remainder. Thus making the overall time complexity of O(k). The space complexity is also O(K) because the StringBuilder stores at most K digits.

Approach: Using Breadth First Search

The greedy approach iterates through all possible digits at each step, which is inefficient and complex. We can find the shortest possible integer that is divisible by k using the BFS approach. Observe the below steps to solve the problem.

Step 1: Check if k is divisible by 2 or 5. If so, return -1.

Step 2: Create a queue to keep track of the remainders as we construct the numbers made up only of 1s.

Step 3: Create a set to store remainders we have already visited to prevent cycles and infinite loops.

Step 4: Initialize the queue with the remainder of 1 % k (which is simply 1), as the first number is just 1.

Step 5: Set the variable named lnth to 1 since the first number is of length 1 (i.e., '1').

Step 6: While the queue is not empty:

Step 6.1: Dequeue an element named remainder from the queue.

Step 6.2: Check if the remainder is 0. If yes, then the current number made of '1's is divisible by k is found, return the current length.

Step 6.3: If the remainder has not been visited before (i.e., not present in the set):

Step 6.3.1: Mark the remainder as visited by adding it to the set.

Step 6.3.2: Calculate the new remainder when appending another '1' to the number, which is (remainder * 10 + 1) % k.

Step 6.3.3: Add this new remainder to the queue and increment the length by 1.

Step 7: If the queue becomes empty without finding a remainder of 0, return -1, indicating no valid number exists.

Output:

 The Smallest integer divisible by 7 is : 6 The Smallest integer divisible by 11 is : 2 The Smallest integer divisible by 5 is : -1 

Complexity Analysis

The time complexity is O(k) because the queue stores up to k remainders, and each remainder is processed once. For each remainder, we perform constant time operations: checking if it is zero, adding it to the visited set, and computing the next remainder, all of which take O(1) time. The space complexity is O(k) because space is required to store up to k remainders in the queue and the visited set.

Approach: Using Hash Table

The BFS approach requires extra space to store visited remainders. So, let us optimise it by using HashMap to store remainders while ensuring we do not loop infinitely. The below steps will guide us to solve the problem.

Step 1: Check if k is divisible by 2 or 5. If yes, return -1.

Step 2: Initialize variables named num = 1 % k to store the remainder when 1 is divided by k and length with 1 to store the number of digits in the sequence.

Step 3: Iterate to find the smallest number divisible by k:

Step 3.1: While num is not 0:

Step 3.1.1: Multiply num by 10 and add 1 to extend the sequence.

Step 3.1.2: Update num = (num * 10 + 1) % k to store the new remainder.

Step 3.1.3: Increment length by 1.

Step 4: When num becomes 0, return length as the length of the smallest number divisible by k.

Output:

 The Smallest integer divisible by 7 is : 6 The Smallest integer divisible by 11 is : 2 The Smallest integer divisible by 5 is : -1 

Complexity Analysis

The program takes O(k) time because the remainder, named num, can take at most k different values from 0 to k – 1 before either finding a divisible number or repeating zero. Each iteration performs a constant time modulo operation. Therefore, the overall time complexity is O(k). The space complexity is O(1) because only a few integer variables are used.

Approach: Using Modulo Remainder

The previous approach still requires space to store remainders. Instead of storing past remainders, we can only store the current remainder at each step using the Modulo Remainder approach. The below steps can be used to solve the problem.

Step 1: Create a HashMap named hm to store remainders and track cycles.

Step 2: Initialize a variable named r as remainder to 0, which will store the remainder when the number made up of only digit 1 is divided by k.

Step 3: Initialize a variable named c to 0, which will store the number of digits (1's) in the repunit.

Step 4: Iterate as long as the remainder r is not 0 or the count of digits c is still 0

Step 5: In each iteration of the loop, append '1' to the number by updating the remainder r:

Step 5.1: Compute r = r % k to get the remainder after division.

Step 5.2: If the remainder r is found in the HashMap, a cycle is detected, so return -1.

Step 5.3: Otherwise, store r in the HashMap.

Step 5.4: Increment the count of c to store the number of digits in the sequence of 1’s.

Step 6: If a valid sequence of 1’s is found that is divisible by k, return c i.e., its length.

Step 6.1: If a cycle is detected, then return -1.

Output:

 The Smallest integer divisible by 7 is : 6 The Smallest integer divisible by 11 is : 2 The Smallest integer divisible by 5 is : -1 

Complexity Analysis

The time complexity of this approach is O(k) because, in the worst case, we may need to check up to k different remainders before finding a divisible number or detecting a cycle. The space complexity is O(k) because it stores the remainders in a set to track cycles and avoid infinite loops.