Question

In: Computer Science

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:


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.
Python: Write a recursive function that accepts an integer argument, n. The function should display n...
Python: Write a recursive function that accepts an integer argument, n. The function should display n lines of asterisks on the screen, with the first line showing 1 asterisk, the second line showing 2 asterisks, up to the nth line which shows n asterisks. Test the function.
1 Write a Java method that takes an integer, n, as input and returns a reference...
1 Write a Java method that takes an integer, n, as input and returns a reference to an array of n random doubles between 100.0 and 200.0. Just write the method. 2. You have a class A: public class A { int i, double d; public A(double d) { this.d=d; this.i=10; } }
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...
Write a function in python that takes in an integer n and computes the left hand...
Write a function in python that takes in an integer n and computes the left hand Riemann sum of the function f(x) = x^2 on the interval [0,1]. Hint: compute the error from the true answer
python exercise: a. Write a function sumDigits that takes a positive integer value and returns the...
python exercise: a. Write a function sumDigits that takes a positive integer value and returns the total sum of the digits in the integers from 1 to that number inclusive. b. Write a program to input an integer n and call the above function in part a if n is positive, else give ‘Value must be Positive’ message. sample: Enter a positive integer: 1000000 The sum of the digits in the number from 1 to 1000000 is 27000001 Enter a...
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
Write a Scheme function that takes a positive integer n and returns the list of all...
Write a Scheme function that takes a positive integer n and returns the list of all first n positive integers in decreasing order: (decreasing-numbers 10) (10 9 8 7 6 5 4 3 2 1) Please explain every step
Write in Racket language. Write a non-recursive Racket function called "keep-short-norec" that takes an integer and...
Write in Racket language. Write a non-recursive Racket function called "keep-short-norec" that takes an integer and a list of strings as parameters and evaluates to a list of strings. The resulting list should be all strings on the original list, maintaining their relative order, whose string length is less than the integer parameter. For example, (keep-short-rec 3 '('abc' 'ab' 'a')) should evaluate to '('ab''a') because these are the only strings shorter than 3.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT