Answer:
Here is the recursive method NoOfOnes :
public static int NoOfOnes(int N) { // method that takes number N as argument and returns the number of 1’s in the binary representation of N
if(N==0) { //base case 1
return 0; } //if the value of N is equal to 0 then method returns 0
else if(N==1){ //base case 2
return 1; } // if the value of N is equal to 1 then method returns 1
else if(N%2==1) { //if N is odd (recursive case)
return NoOfOnes(N/2)+1; } //calls method recursively and divides N by 2 plus 1
else{ //when N i even (recursive case)
return NoOfOnes(N/2); } } //calls method recursively and divides N by 2 to return number of 1's in binary representation of N
Explanation:
Here is the complete JAVA program:
import java.util.Scanner; //to take input from user
public class Main {
public static int NoOfOnes(int N) {//the method that takes number N as argument and returns the number of 1’s in the binary representation of N
if(N==0) { //base case 1
return 0; }
else if(N==1){//base case 2
return 1; }
else if(N%2==1) {//recursive case when N is odd
return NoOfOnes(N/2)+1; }
else{ //recursive case when N is even
return NoOfOnes(N/2); } }
public static void main(String[] args) { //start of main function
Scanner scan = new Scanner(System.in); //creates object of Scanner
System.out.print("Enter n: ");//prompts user to enter value of N
int n = scan.nextInt(); //reads the value of n from use
System.out.print("number of 1’s in the binary representation of " +n+" is: "+NoOfOnes(n)); } } //displays the number of 1’s in the binary representation of n
i will explain the working of the function with an example
Lets say N = 6
if(N==0) this statement evaluates to false as N is not 0
else if(N==1 this statement also evaluates to false as N is not 1
else if(N%2==1) this statement also evaluates to false because N is not odd. If we take modulo of 6 by 2 then the remainder is 0 because 6 is completely divisible by 2 so N = 6 is an even number. So the else part is executed:
else{
return NoOfOnes(N/2);}
This statement calls NoOfOnes recursive by passing N/2 to the method. So this becomes:
return NoOfOnes(6/2)
6/2 = 3
NoOfOnes(3)
Now this method is called again with the value of N = 3. Since 3 is an odd number so the recursive case of odd N is executed:
else if(N%2==1) {
return NoOfOnes(N/2)+1; }
NoOfOnes(3/2)+ 1
NoOfOnes(1) + 1
Now the method is called again with value of N=1. The base case 2 is executed because N==1 which returns 1
else if(N==1){
return 1; }
So this becomes
NoOfOnes(1) + 1
1 + 1
= 2
So the method return 2 as the number of 1’s in the binary representation of N = 6
Hence the output of the above program with N = 6 is
number of 1’s in the binary representation of 6 is: 2
