CSES Solutions – Digit Queries
Consider an infinite string that consists of all positive integers in increasing order: [12345678910111213141516171819202122232425…]. The task is to process Q queries of the form: return the Nth digit of the infinite string sequence.
Example:
Input: Q = 3, queries[] = {7, 19, 12}
Output: 7 4 1
Explanation:
- Query 1: The 7th digit is 7. The first 9 digits are just the numbers from 1 to 9.
- Query 2: The 19th digit is 4. The first 9 digits are the numbers from 1 to 9. The next 10 digits are the numbers from 10 to 14. So, the 19th digit, which is the 10th digit in the second part, is 4 from the number 14.
- Query 3: The 12th digit is 1. The first 9 digits are the numbers from 1 to 9. The 10th digit is 1 from the number 10, the 11th digit is 0 from the number 10 and the 12th digit is 1 from the number 11.
Input: Q = 2, queries[] = {92, 152}
Output: 5 8
Explanation:
- Query 1: The 92nd digit is 5 from the number 51.
- Query 2: The 152nd digit is 8 from the number 81.
Approach: To solve the problem, follow the idea below:
The idea is to divide the problem in three parts:
- Find the interval in which the Nth digit lies.
- Calculate the number which contains the Nth digit.
- Find out which digit in the number is the result.
Identify the interval in which the Nth digit is located by calculating the number of digits in each interval. For instance, there are 9 (1*9) digits in the interval 1 – 9, 180 (2*90) digits in the interval 10 – 99, 2700 (3*900) digits in the interval 100 – 999, and so on. Subtract N with the number of digits in the interval (base*digits) and stop if it is less than zero. Now to find the target number, we know that the first ‘d’ digit number would be 10^(d-1), adding (N-1)/d to it would give us our target number. Index of the Nth digit is N % d. If index equals to 0, it means the target digit is the last digit of number else divide the target number by 10^(digits – index) and return the last digit which is our result.
Step-by-step algorithm:
- Initialize digits as 1 to store the number of digits in the current interval.
- Initialize base as 9 to store the total numbers in the current digit interval.
- Subtract N with the number of digits in the interval (base*digits) and stop if it is less than zero.
- Calculate index as the remainder of N divided by digits. This represents the position of the Nth digit in the number.
- Calculate the number which contains the Nth digit as 10^(digits – 1) + (N – 1) / digits.
- Find out which digit in the number is the result by dividing res by 10^(digits – index).
- Return res % 10 which is the Nth digit.
Below is the implementation of the above algorithm:
#include <bits/stdc++.h>
using namespace std;
// Function to calculate a^b using binary exponentiation
long long power(long long a, long long b)
{
// If b = 0, whatever be the value of a,
// our result will be 1.
long long res = 1;
while (b > 0) {
// If b is an odd number, then
// (a^b) = (a * (a^(b–1)/2)^2)
if (b & 1) {
res = (res * a);
}
// If b is an even number, then
// (a^b) = ((a^2)^(b/2))
a = (a * a);
b >>= 1;
}
return res;
}
long long findDigit(long long int N)
{
// No of digits
long long digits = 1;
// Total numbers in current digit interval
long long base = 9;
// Find the interval in which the Nth digit lies
while (N - digits * base > 0) {
N -= digits * base;
base *= 10;
digits++;
}
long long index = N % digits;
// Calculate the number which contains the Nth digit
long long res
= power(10, (digits - 1)) + (N - 1) / digits;
// Find out which digit in the number is the result
if (index != 0)
res = res / power(10, digits - index);
return res % 10;
}
// Drive Code
int main()
{
// Example 1
long long q = 3;
int queries[q] = { 7, 19, 12 };
for (int i = 0; i < q; i++)
cout << findDigit(queries[i]) << " ";
cout << endl;
return 0;
}
public class Main {
// Function to calculate a^b using binary exponentiation
static long power(long a, long b) {
// If b = 0, whatever be the value of a,
// our result will be 1.
long res = 1;
while (b > 0) {
// If b is an odd number, then
// (a^b) = (a * (a^(b–1)/2)^2)
if ((b & 1) == 1) {
res = (res * a);
}
// If b is an even number, then
// (a^b) = ((a^2)^(b/2))
a = (a * a);
b >>= 1;
}
return res;
}
static long findDigit(long N) {
// No of digits
long digits = 1;
// Total numbers in the current digit interval
long base = 9;
// Find the interval in which the Nth digit lies
while (N - digits * base > 0) {
N -= digits * base;
base *= 10;
digits++;
}
long index = N % digits;
// Calculate the number which contains the Nth digit
long res = power(10, (digits - 1)) + (N - 1) / digits;
// Find out which digit in the number is the result
if (index != 0)
res = res / power(10, digits - index);
return res % 10;
}
// Drive Code
public static void main(String[] args) {
// Example 1
int q = 3;
long[] queries = {7, 19, 12};
for (int i = 0; i < q; i++)
System.out.print(findDigit(queries[i]) + " ");
System.out.println();
}
}
// This code is contributed by shivamgupta310570
# -*- coding: utf-8 -*-
def power(a, b):
# If b = 0, whatever be the value of a,
# our result will be 1.
res = 1
while b > 0:
# If b is an odd number, then
# (a^b) = (a * (a^(b–1)/2)^2)
if b & 1:
res *= a
# If b is an even number, then
# (a^b) = ((a^2)^(b/2))
a *= a
b >>= 1
return res
def find_digit(N):
# No of digits
digits = 1
# Total numbers in current digit interval
base = 9
# Find the interval in which the Nth digit lies
while N - digits * base > 0:
N -= digits * base
base *= 10
digits += 1
index = N % digits
# Calculate the number which contains the Nth digit
res = power(10, digits - 1) + (N - 1) // digits
# Find out which digit in the number is the result
if index != 0:
res //= 10 ** (digits - index)
return res % 10
# Driver Code
if __name__ == "__main__":
# Example 1
queries = [7, 19, 12]
for query in queries:
print find_digit(query),
print
using System;
public class Program
{
// Function to calculate a^b using binary exponentiation
static long Power(long a, long b)
{
// If b = 0, whatever be the value of a,
// our result will be 1.
long res = 1;
while (b > 0)
{
// If b is an odd number, then
// (a^b) = (a * (a^(b–1)/2)^2)
if ((b & 1) == 1)
{
res = (res * a);
}
// If b is an even number, then
// (a^b) = ((a^2)^(b/2))
a = (a * a);
b >>= 1;
}
return res;
}
static long FindDigit(long N)
{
// No of digits
long digits = 1;
// Total numbers in current digit interval
long baseVal = 9;
// Find the interval in which the Nth digit lies
while (N - digits * baseVal > 0)
{
N -= digits * baseVal;
baseVal *= 10;
digits++;
}
long index = N % digits;
// Calculate the number which contains the Nth digit
long res = Power(10, (digits - 1)) + (N - 1) / digits;
// Find out which digit in the number is the result
if (index != 0)
res = res / Power(10, digits - index);
return res % 10;
}
// Drive Code
public static void Main()
{
// Example 1
int q = 3;
long[] queries = { 7, 19, 12 };
for (int i = 0; i < q; i++)
Console.Write(FindDigit(queries[i]) + " ");
Console.WriteLine();
}
}
// Function to calculate a^b using binary exponentiation
function power(a, b) {
// If b = 0, whatever be the value of a,
// our result will be 1.
let res = 1;
while (b > 0) {
// If b is an odd number, then
// (a^b) = (a * (a^(b–1)/2)^2)
if (b & 1) {
res *= a;
}
// If b is an even number, then
// (a^b) = ((a^2)^(b/2))
a *= a;
b >>= 1;
}
return res;
}
function findDigit(N) {
// No of digits
let digits = 1;
// Total numbers in current digit interval
let base = 9;
// Find the interval in which the Nth digit lies
while (N - digits * base > 0) {
N -= digits * base;
base *= 10;
digits++;
}
let index = N % digits;
// Calculate the number which contains the Nth digit
let res = power(10, digits - 1) + Math.floor((N - 1) / digits);
// Find out which digit in the number is the result
if (index !== 0)
res = Math.floor(res / power(10, digits - index));
return res % 10;
}
// Drive Code
let q = 3;
let queries = [7, 19, 12];
let output = '';
for (let i = 0; i < q; i++)
output += findDigit(queries[i]) + " ";
console.log(output);
Output
7 4 1
Time Complexity: O(Q * log(N)), where Q is the number of queries and N is the position of digit given in each query.
Auxiliary Space: O(1)