Given two integers N and K, the task is to find the count of set bits in the Kth number in the Odd-Even sequence made of the number from the range [1, N]. The Odd-Even sequence first contains all the odd numbers from 1 to N and then all the even numbers from 1 to N.
Examples:
Input: N = 8, K = 4
Output: 3
The sequence is 1, 3, 5, 7, 2, 4, 6 and 8.
4th element is 7 and the count
of set bits in it is 3.
Input: N = 18, K = 12
Output: 2
Approach: An approach to find the Kth element of the required sequence has been discussed in this article. So, find the required number and then use __builtin_popcount() to find the count of set bits in it.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the kth element// of the Odd-Even sequence// of length nint findK(int n, int k){ int pos; // Finding the index from where the // even numbers will be stored if (n % 2 == 0) { pos = n / 2; } else { pos = (n / 2) + 1; } // Return the kth element if (k <= pos) { return (k * 2 - 1); } else return ((k - pos) * 2);}// Function to return the count of// set bits in the kth number of the// odd even sequence of length nint countSetBits(int n, int k){ // Required kth number int kth = findK(n, k); // Return the count of set bits return __builtin_popcount(kth);}// Driver codeint main(){ int n = 18, k = 12; cout << countSetBits(n, k); return 0;} |
Java
// Java implementation of the approach class GFG{ // Function to return the kth element // of the Odd-Even sequence // of length n static int findK(int n, int k) { int pos; // Finding the index from where the // even numbers will be stored if (n % 2 == 0) { pos = n / 2; } else { pos = (n / 2) + 1; } // Return the kth element if (k <= pos) { return (k * 2 - 1); } else return ((k - pos) * 2); } // Function to return the count of // set bits in the kth number of the // odd even sequence of length n static int countSetBits(int n, int k) { // Required kth number int kth = findK(n, k); int count = 0; while (kth > 0) { count += kth & 1; kth >>= 1; } // Return the count of set bits return count; } // Driver code public static void main (String[] args) { int n = 18, k = 12; System.out.println(countSetBits(n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the kth element # of the Odd-Even sequence # of length n def findK(n, k) : # Finding the index from where the # even numbers will be stored if (n % 2 == 0) : pos = n // 2; else : pos = (n // 2) + 1; # Return the kth element if (k <= pos) : return (k * 2 - 1); else : return ((k - pos) * 2); # Function to return the count of # set bits in the kth number of the # odd even sequence of length n def countSetBits( n, k) : # Required kth number kth = findK(n, k); # Return the count of set bits return bin(kth).count('1'); # Driver code if __name__ == "__main__" : n = 18; k = 12; print(countSetBits(n, k)); # This code is contributed by kanugargng |
C#
// C# implementation of the above approach using System;class GFG{ // Function to return the kth element // of the Odd-Even sequence // of length n static int findK(int n, int k) { int pos; // Finding the index from where the // even numbers will be stored if (n % 2 == 0) { pos = n / 2; } else { pos = (n / 2) + 1; } // Return the kth element if (k <= pos) { return (k * 2 - 1); } else return ((k - pos) * 2); } // Function to return the count of // set bits in the kth number of the // odd even sequence of length n static int countSetBits(int n, int k) { // Required kth number int kth = findK(n, k); int count = 0; while (kth > 0) { count += kth & 1; kth >>= 1; } // Return the count of set bits return count; } // Driver code public static void Main (String[] args) { int n = 18, k = 12; Console.WriteLine(countSetBits(n, k)); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Function to return the kth element // of the Odd-Even sequence // of length n function findK(n, k) { let pos; // Finding the index from where the // even numbers will be stored if (n % 2 == 0) { pos = parseInt(n / 2, 10); } else { pos = parseInt(n / 2, 10) + 1; } // Return the kth element if (k <= pos) { return (k * 2 - 1); } else { return ((k - pos) * 2); } } // Function to return the count of // set bits in the kth number of the // odd even sequence of length n function countSetBits(n, k) { // Required kth number let kth = findK(n, k); let count = 0; while (kth > 0) { count += kth & 1; kth >>= 1; } // Return the count of set bits return count; } let n = 18, k = 12; document.write(countSetBits(n, k)); </script> |
Output:
2
Time Complexity: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
