PYTHON 3: Write a recursive function that takes a non-negative integer n as input and returns...

PYTHON 3:

Write a recursive function that takes a non-negative integer n as input and returns the number of 1's in the binary representation of n.

Use the fact that this is equal to the number of 1's in the representation of n//2 (integer division) plus 1 if n is odd.

>>>numOnes(0)
0
>>>numOnes(1)
1
>>>numOnes(14)
3

Solutions

Expert Solution

def numOnes(n): #function
if n==0:
return (0) #base cases
elif n == 1:
return (1)
else:
return numOnes(n//2)+numOnes(n%2) #recursive call

print(numOnes(0))
print(numOnes(1))
print(numOnes(14))

output:

venereology answered 1 year ago

Next > < Previous

Related Solutions

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

USING PYTHON, write a function that takes a list of integers as input and returns a...

USING PYTHON, write a function that takes a list of integers as input and returns a list with only the even numbers in descending order (Largest to smallest) Example: Input list: [1,6,3,8,2,5] List returned: [8, 6, 2]. DO NOT use any special or built in functions like append, reverse etc.

Write a C function called weighted_digit_sum that takes a single integer as input, and returns a...

Write a C function called weighted_digit_sum that takes a single integer as input, and returns a weighted sum of that numbers digits. The last digit of the number (the ones digit) has a weight of 1, so should be added to the sum "as is". The second from last digit (the tens digit) has a weight of 2, and so should be multiplied by 2 then added to the sum. The third from last digit should be multiplied by 1...

python 3 please Define a function voweliest that takes as input a string and returns as...

python 3 please Define a function voweliest that takes as input a string and returns as output a tuple where the string that has the most vowels in it is the first element and the second is the number of vowels in that string. Note: don't worry about ties or capital letters Hint: consider defining and using a separate function that counts the number of vowels in a given string

IN PYTHON Write a program that takes in a positive integer as input, and outputs a...

IN PYTHON Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is: As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x // 2 Note: The above algorithm outputs the 0's and 1's in reverse order. You will need to write a second function to reverse the string....

Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters...

Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters in mystring that also occur in the string ‘Python’. Using above function, write a program that repeatedly prompts the user for a string and then prints the number of letters in the string that are also in string ‘Python’. The program terminates when the user types an empty string.

In python, write a function, called ThreeSum, that accepts a list of non-negative numbers as input,...

In python, write a function, called ThreeSum, that accepts a list of non-negative numbers as input, and returns the highest sum of three neighboring elements in it. Write a main method that initializes the following five lists, gets the ThreeSum result for all of them using the above function, and prints the result to the screen. Example of the output: List 1: [4,5,4,5] , Three sum = 14 List 2: [7] , Three sum = 7 List 3: [ ]...

Write a recursive function in C++ named multiplyNumbers, which takes one int argument n as input...

Write a recursive function in C++ named multiplyNumbers, which takes one int argument n as input and returns the product of numbers from 1 to n.

I have a python coding question: Write the function: eAapproximately (n), that takes a positive integer...

I have a python coding question: Write the function: eAapproximately (n), that takes a positive integer value n and returns an approximation of e as (1 + 1/n)^n I am not even sure what the question is asking me to do but I think it is asking me to code that function. Does anyone know how to do this?

Write a recursive method using Java that takes a string s as input and returns a...

Write a recursive method using Java that takes a string s as input and returns a list that contains all the anagrams of the string s. An anagram is a word formed by rearranging the letters of a different word. For instance, the word ‘cat’ is an anagram of ‘act’. Notice that the output list cannot contain duplicates.

Subjects