Given an integer N, the task is to print the first K multiples of N using Bitwise Operators.
Examples:
Input: N = 16, K = 7
Output:
16 * 1 = 16
16 * 2 = 32
16 * 3 = 48
16 * 4 = 64
16 * 5 = 80
16 * 6 = 96
16 * 7 = 112
Input: N = 7, K = 10
Output:
7 * 1 = 7
7 * 2 = 14
7 * 3 = 21
7 * 4 = 28
7 * 5 = 35
7 * 6 = 42
7 * 7 = 49
7 * 8 = 56
7 * 9 = 63
7 * 10 = 70
Approach:
Follow the steps below to solve the problem:
- Iterate up to K.
- For each iteration, print current value of N.
- Then, calculate the sum of 2i for every ith set bit of N. Add this sum to N and repeat from the step above.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to print the first K // multiples of N void Kmultiples( int n, int k) { int a = n; for ( int i = 1; i <= k; i++) { // Print the value of N*i cout << n << " * " << i << " = " << a << endl; int j = 0; // Iterate each bit of N and add // pow(2, pos), where pos is the // index of each set bit while (n >= (1 << j)) { // Check if current bit at // pos j is fixed or not a += n & (1 << j); // For next set bit j++; } } } // Driver Code int main() { int N = 16, K = 7; Kmultiples(N, K); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to print the first K // multiples of N static void Kmultiples( int n, int k) { int a = n; for ( int i = 1 ; i <= k; i++) { // Print the value of N*i System.out.print(n+ " * " + i+ " = " + a + "\n" ); int j = 0 ; // Iterate each bit of N and add // Math.pow(2, pos), where pos is the // index of each set bit while (n >= ( 1 << j)) { // Check if current bit at // pos j is fixed or not a += n & ( 1 << j); // For next set bit j++; } } } // Driver Code public static void main(String[] args) { int N = 16 , K = 7 ; Kmultiples(N, K); } } // This code is contributed by Rohit_ranjan |
Python3
# Python3 program to implement # the above approach # Function to print the first K # multiples of N def Kmultiples(n, k): a = n for i in range ( 1 , k + 1 ): # Print the value of N*i print ( "{} * {} = {}" . format (n, i, a)) j = 0 # Iterate each bit of N and add # pow(2, pos), where pos is the # index of each set bit while (n > = ( 1 << j)): # Check if current bit at # pos j is fixed or not a + = n & ( 1 << j) # For next set bit j + = 1 # Driver Code N = 16 K = 7 Kmultiples(N, K) # This code is contributed by Shivam Singh |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to print the first K // multiples of N static void Kmultiples( int n, int k) { int a = n; for ( int i = 1; i <= k; i++) { // Print the value of N*i Console.Write(n + " * " + i + " = " + a + "\n" ); int j = 0; // Iterate each bit of N and add // Math.Pow(2, pos), where pos is // the index of each set bit while (n >= (1 << j)) { // Check if current bit at // pos j is fixed or not a += n & (1 << j); // For next set bit j++; } } } // Driver Code public static void Main(String[] args) { int N = 16, K = 7; Kmultiples(N, K); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // javascript program to implement // the above approach // Function to print the first K // multiples of N function Kmultiples(n , k) { var a = n; for (i = 1; i <= k; i++) { // Print the value of N*i document.write(n+ " * " + i+ " = " + a + "<br>" ); var j = 0; // Iterate each bit of N and add // Math.pow(2, pos), where pos is the // index of each set bit while (n >= (1 << j)) { // Check if current bit at // pos j is fixed or not a += n & (1 << j); // For next set bit j++; } } } // Driver Code var N = 16, K = 7; Kmultiples(N, K); // This code contributed by Princi Singh </script> |
16 * 1 = 16 16 * 2 = 32 16 * 3 = 48 16 * 4 = 64 16 * 5 = 80 16 * 6 = 96 16 * 7 = 112
Time Complexity: O(Klog2N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!