Given a decimal number n without floating-point. The problem is to convert the decimal number to octal number with minimum use of arithmetic operators.
Examples:
Input : n = 10 Output : 12 12 is octal equivalent of decimal 10. Input : n = 151 Output : 227
Approach: Following are the steps:
- Perform decimal to binary conversion without using arithmetic operators of the given number n. Refer this post. Let this number be bin.
- Convert the binary number bin to octal. Refer this post.
C++
// C++ implementation of decimal to octal conversion// with minimum use of arithmetic operators#include <bits/stdc++.h>using namespace std;// function for decimal to binary conversion// without using arithmetic operatorsstring decToBin(int n){ if (n == 0) return "0"; // to store the binary equivalent of decimal string bin = ""; while (n > 0) { // to get the last binary digit of the // number 'n' and accumulate it at the // beginning of 'bin' bin = ((n & 1) == 0 ? '0' : '1') + bin; // right shift 'n' by 1 n >>= 1; } // required binary number return bin;} // Function to find octal equivalent of binarystring convertBinToOct(string bin){ int l = bin.size(); // add min 0's in the beginning to make // string length divisible by 3 for (int i = 1; i <= (3 - l % 3) % 3; i++) bin = '0' + bin; // create map between binary and its // equivalent octal code unordered_map<string, char> bin_oct_map; bin_oct_map["000"] = '0'; bin_oct_map["001"] = '1'; bin_oct_map["010"] = '2'; bin_oct_map["011"] = '3'; bin_oct_map["100"] = '4'; bin_oct_map["101"] = '5'; bin_oct_map["110"] = '6'; bin_oct_map["111"] = '7'; int i = 0; string octal = ""; while (1) { // one by one extract from left, substring // of size 3 and add its octal code octal += bin_oct_map[bin.substr(i, 3)]; i += 3; if (i == bin.size()) break; } // required octal number return octal; }// function to find octal equivalent of decimalstring decToOctal(int n){ // convert decimal to binary string bin = decToBin(n); // convert binary to octal // required octal equivalent of decimal return convertBinToOct(bin);}// Driver program to test aboveint main(){ int n = 151; cout << decToOctal(n); return 0;} |
Java
// Java implementation of decimal to octal // conversion with minimum use of // arithmetic operatorsimport java.util.*;class GFG {// function for decimal to binary conversion// without using arithmetic operatorsstatic String decToBin(int n){ if (n == 0) return "0"; // to store the binary equivalent of decimal String bin = ""; while (n > 0) { // to get the last binary digit of the // number 'n' and accumulate it at the // beginning of 'bin' bin = ((n & 1) == 0 ? '0' : '1') + bin; // right shift 'n' by 1 n >>= 1; } // required binary number return bin;}// Function to find octal equivalent of binarystatic String convertBinToOct(String bin){ int l = bin.length(); // add min 0's in the beginning to make // string length divisible by 3 for (int i = 1; i <= (3 - l % 3) % 3; i++) bin = '0' + bin; // create map between binary and its // equivalent octal code Map<String, Character> bin_oct_map = new HashMap<>(); bin_oct_map.put("000", '0'); bin_oct_map.put("001", '1'); bin_oct_map.put("010", '2'); bin_oct_map.put("011", '3'); bin_oct_map.put("100", '4'); bin_oct_map.put("101", '5'); bin_oct_map.put("110", '6'); bin_oct_map.put("111", '7'); int i = 0; String octal = ""; while (true) { // one by one extract from left, substring // of size 3 and add its octal code octal += bin_oct_map.get(bin.substring(i, i + 3)); i += 3; if (i == bin.length()) break; } // required octal number return octal; }// function to find octal equivalent of decimalstatic String decToOctal(int n){ // convert decimal to binary String bin = decToBin(n); // convert binary to octal // required octal equivalent of decimal return convertBinToOct(bin);}// Driver Codepublic static void main(String[] args) { int n = 151; System.out.println(decToOctal(n));}} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of decimal to octal conversion# with minimum use of arithmetic operators# function for decimal to binary conversion# without using arithmetic operatorsdef decToBin(n): if (n == 0): return "0" # to store the binary equivalent of decimal bin = "" while (n > 0): # to get the last binary digit of the # number 'n' and accumulate it at the # beginning of 'bin' bin = ('0' if(n & 1) == 0 else '1') + bin # right shift 'n' by 1 n >>= 1 # required binary number return bin# Function to find octal equivalent of binarydef convertBinToOct(bin): l = len(bin) # add min 0's in the beginning to make # string length divisible by 3 for i in range(1,((3 - l % 3) % 3) + 1): bin = '0' + bin # create map between binary and its # equivalent octal code bin_oct_map = dict() bin_oct_map["000"] = '0' bin_oct_map["001"] = '1' bin_oct_map["010"] = '2' bin_oct_map["011"] = '3' bin_oct_map["100"] = '4' bin_oct_map["101"] = '5' bin_oct_map["110"] = '6' bin_oct_map["111"] = '7' i = 0 octal = "" while (True): # one by one extract from left, substring # of size 3 and add its octal code octal += bin_oct_map[bin[i:i + 3]] i += 3 if (i == len(bin)): break # required octal number return octal# function to find octal equivalent of decimaldef decToOctal(n): # convert decimal to binary bin = decToBin(n) # convert binary to octal # required octal equivalent of decimal return convertBinToOct(bin)# Driver program to test aboveif __name__=='__main__': n = 151 print(decToOctal(n)) # This code is contributed by pratham76 |
C#
// C# implementation of decimal to octal // conversion with minimum use of // arithmetic operatorsusing System;using System.Collections.Generic; class GFG{ // Function for decimal to binary// conversion without using // arithmetic operatorsstatic string decToBin(int n){ if (n == 0) return "0"; // To store the binary equivalent // of decimal string bin = ""; while (n > 0) { // To get the last binary digit of the // number 'n' and accumulate it at the // beginning of 'bin' bin = ((n & 1) == 0 ? '0' : '1') + bin; // Right shift 'n' by 1 n >>= 1; } // Required binary number return bin;} // Function to find octal equivalent of binarystatic string convertBinToOct(string bin){ int l = bin.Length; // Add min 0's in the beginning to make // string length divisible by 3 for(int j = 1; j <= (3 - l % 3) % 3; j++) bin = '0' + bin; // Create map between binary and its // equivalent octal code Dictionary<string, char> bin_oct_map = new Dictionary<string, char>(); bin_oct_map.Add("000", '0'); bin_oct_map.Add("001", '1'); bin_oct_map.Add("010", '2'); bin_oct_map.Add("011", '3'); bin_oct_map.Add("100", '4'); bin_oct_map.Add("101", '5'); bin_oct_map.Add("110", '6'); bin_oct_map.Add("111", '7'); int i = 0; string octal = ""; while (true) { // One by one extract from left, substring // of size 3 and add its octal code octal += bin_oct_map[bin.Substring(i, 3)]; i += 3; if (i == bin.Length) break; } // Required octal number return octal; } // Function to find octal equivalent of decimalstatic string decToOctal(int n){ // Convert decimal to binary string bin = decToBin(n); // Convert binary to octal // required octal equivalent // of decimal return convertBinToOct(bin);} // Driver Codepublic static void Main(string[] args) { int n = 151; Console.Write(decToOctal(n));}} // This code is contributed by rutvik_56 |
Javascript
<script>// Javascript implementation of decimal to octal conversion// with minimum use of arithmetic operators// function for decimal to binary conversion// without using arithmetic operatorsfunction decToBin(n){ if (n == 0) return "0"; // to store the binary equivalent of decimal var bin = ""; while (n > 0) { // to get the last binary digit of the // number 'n' and accumulate it at the // beginning of 'bin' bin = ((n & 1) == 0 ? '0' : '1') + bin; // right shift 'n' by 1 n >>= 1; } // required binary number return bin;} // Function to find octal equivalent of binaryfunction convertBinToOct(bin){ var l = bin.length; // add min 0's in the beginning to make // string length divisible by 3 for (var i = 1; i <= (3 - l % 3) % 3; i++) bin = '0' + bin; // create map between binary and its // equivalent octal code var bin_oct_map = new Map(); bin_oct_map.set("000",'0'); bin_oct_map.set("001",'1'); bin_oct_map.set("010",'2'); bin_oct_map.set("011",'3'); bin_oct_map.set("100",'4'); bin_oct_map.set("101",'5'); bin_oct_map.set("110",'6'); bin_oct_map.set("111",'7'); var i = 0; var octal = ""; while (1) { // one by one extract from left, substring // of size 3 and add its octal code octal += bin_oct_map.get(bin.substring(i, i+3)); i += 3; if (i == bin.length) break; } // required octal number return octal; }// function to find octal equivalent of decimalfunction decToOctal(n){ // convert decimal to binary var bin = decToBin(n); // convert binary to octal // required octal equivalent of decimal return convertBinToOct(bin);}// Driver program to test abovevar n = 151;document.write( decToOctal(n));ing// This code is contributed by itsok.</script> |
Output
227
Time Complexity: O(n), where n is the length of the binary string.
Auxiliary Space: O(n) because using extra space for string octal
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More Info here on that Topic: geeksforgeeks.org/decimal-to-octal-conversion-with-minimum-use-of-arithmetic-operators/ […]