Find the Nth digit from right in base B of the given number in Decimal base

0 0 5 minutes read

Given a number A in decimal base, the task is to find the N^th digit from last in base B
Examples:

Input: A = 100, N = 3, B = 4
Output: 2
Explanation:
(100)₄ = 1210
3^rd digit from last is 2
Input: A = 50, N = 3, B = 5
Output: 2
Explanation:
(50)₅ = 200
3^rd digit from last is 2

Naive Approach: The basic idea is to first convert the decimal number A into base B and then extract the Nth digit from the right of the resulting number.

Implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to compute Nth digit
// from right in base B
int nthDigit(int a, int n, int b)
{
    // Convert A to base B
    int num = 0;
    int power = 0;
    while (a > 0) {
        int digit = a % b;
        num += digit * pow(10, power);
        a /= b;
        power++;
    }
 
    // Extract Nth digit from right
    int digit;
    while (n > 0) {
        digit = num % 10;
        num /= 10;
        n--;
    }
 
    return digit;
}
 
int main()
{
    int a = 100;
    int n = 3;
    int b = 4;
    cout << nthDigit(a, n, b) << endl;
 
    return 0;
}

Java

import java.lang.Math;
 
public class Main {
 
    // Function to compute Nth digit
    // from right in base B
    public static int nthDigit(int a, int n, int b)
    {
        // Convert A to base B
        int num = 0;
        int power = 0;
        while (a > 0) {
            int digit = a % b;
            num += digit * (int)Math.pow(10, power);
            a /= b;
            power++;
        }
 
        // Extract Nth digit from right
        int digit = 0;
        while (n > 0) {
            digit = num % 10;
            num /= 10;
            n--;
        }
 
        return digit;
    }
 
    public static void main(String[] args)
    {
        int a = 100;
        int n = 3;
        int b = 4;
        System.out.println(nthDigit(a, n, b));
    }
}
// This code is contributed by user_dtewbxkn77n

Python3

# Function to compute Nth digit
# from right in base B
 
 
def nthDigit(a, n, b):
    # Convert A to base B
    num = 0
    power = 0
    while a > 0:
        digit = a % b
        num += digit * (10 ** power)
        a //= b
        power += 1
 
    # Extract Nth digit from right
    digit = 0
    while n > 0:
        digit = num % 10
        num //= 10
        n -= 1
 
    return digit
 
 
a = 100
n = 3
b = 4
print(nthDigit(a, n, b))

C#

using System;
 
public class GFG {
   
    // Function to compute Nth digit
    // from right in base B
    public static int nthDigit(int a, int n, int b)
    {
        // Convert A to base B
        int num = 0;
        int power = 0;
        while (a > 0) {
            int digit_ = a % b;
            num += digit_ * (int)Math.Pow(10, power);
            a /= b;
            power++;
        }
 
        // Extract Nth digit from right
        int digit = 0;
        while (n > 0) {
            digit = num % 10;
            num /= 10;
            n--;
        }
 
        return digit;
    }
 
    public static void Main()
    {
        int a = 100;
        int n = 3;
        int b = 4;
        Console.WriteLine(nthDigit(a, n, b));
    }
}
// This code is contributed by prasad264

Javascript

// Function to compute Nth digit from right in base B
function nthDigit(a, n, b) {
  // Convert A to base B
  let num = 0;
  let power = 0;
  while (a > 0) {
    let digit = a % b;
    num += digit * Math.pow(10, power);
    a = Math.floor(a / b);
    power++;
  }
 
  // Extract Nth digit from right
  let digit;
  while (n > 0) {
    digit = num % 10;
    num = Math.floor(num / 10);
    n--;
  }
 
  return digit;
}
 
let a = 100;
let n = 3;
let b = 4;
console.log(nthDigit(a, n, b));

Output

Time Complexity: O(log b(a) + a)
Auxiliary Space: O(1)

Efficient Approach: The idea is to skip (N-1) digits of the given number in base B by dividing the number with B, (N – 1) times and then return the modulo of the current number by the B to get the N^th digit from the right.
Below is the implementation of the above approach:

C++

// C++ Implementation to find Nth digit
// from right in base B
 
#include <iostream>
using namespace std;
 
// Function to compute Nth digit
// from right in base B
int nthDigit(int a, int n, int b)
{
 
    // Skip N-1 Digits in Base B
    for (int i = 1; i < n; i++)
        a = a / b;
 
    // Nth Digit from right in Base B
    return a % b;
}
 
// Driver Code
int main()
{
    int a = 100;
    int n = 3;
    int b = 4;
    cout << nthDigit(a, n, b);
    return 0;
}

Java

// Java Implementation to find Nth digit
// from right in base B
import java.util.*;
 
class GFG
{
 
// Function to compute Nth digit
// from right in base B
static int nthDigit(int a, int n, int b)
{
 
    // Skip N-1 Digits in Base B
    for (int i = 1; i < n; i++)
        a = a / b;
 
    // Nth Digit from right in Base B
    return a % b;
}
 
// Driver Code
public static void main(String[] args)
{
    int a = 100;
    int n = 3;
    int b = 4;
    System.out.print(nthDigit(a, n, b));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 Implementation to find Nth digit
# from right in base B
 
# Function to compute Nth digit
# from right in base B
def nthDigit(a, n, b):
 
    # Skip N-1 Digits in Base B
    for i in range(1, n):
        a = a // b
 
    # Nth Digit from right in Base B
    return a % b
 
# Driver Code
a = 100
n = 3
b = 4
print(nthDigit(a, n, b))
 
# This code is contributed by ApurvaRaj

C#

// C# Implementation to find Nth digit
// from right in base B
using System;
 
class GFG
{
 
    // Function to compute Nth digit
    // from right in base B
    static int nthDigit(int a, int n, int b)
    {
     
        // Skip N-1 Digits in Base B
        for (int i = 1; i < n; i++)
            a = a / b;
     
        // Nth Digit from right in Base B
        return a % b;
    }
     
    // Driver Code
    public static void Main()
    {
        int a = 100;
        int n = 3;
        int b = 4;
        Console.Write(nthDigit(a, n, b));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript Implementation to find Nth digit 
// from right in base B 
 
// Function to compute Nth digit 
// from right in base B 
function nthDigit(a, n, b) 
{ 
 
    // Skip N-1 Digits in Base B 
    for (var i = 1; i < n; i++) 
        a = parseInt(a / b); 
 
    // Nth Digit from right in Base B 
    return a % b; 
} 
 
// Driver Code 
var a = 100; 
var n = 3; 
var b = 4; 
document.write(nthDigit(a, n, b)); 
 
// This code is contributed by rutvik_56.
</script>

Output

Time Complexity: O(N)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!