Programming challenge “Greatest Odd Divisor”

Question

I am trying to solve a programming problem on a coding platform. When I submit the code on the coding platform, it throws a "Time Limit Exceeded" error. Can someone check my solution and help optimize it?

A food delivery company X gets a lot of orders every day. It charges some commission from the restaurants on these orders. More formally, if an order value is K, X charges a commission which is the greatest odd divisor of K. You can assume that an order value will always be an integer. Given an order value N, and let C(N) be the greatest odd-divisor of N, output the value of C(1) + C(2) + C(3) + … + C(N).

INPUT : Input will be an integer, N, the order value. 1 <= N <= 10^9

OUTPUT : Single integer which is the answer

import java.util.*;
public class Solution {
    static double GOD(double num)
    {
        if(num%2!=0)
        {
            return num;
        }
        else
        {
            for (double i = num / 2; i > 0 ;i--)
            {
                if (num % i == 0 && i % 2 != 0)
                {
                    return i;
                }
            }
            return 0;
        }
     }
public static void main(String args[] ) throws Exception {
   
    Scanner sc = new Scanner(System.in);
    double num = sc.nextDouble();
    double sum = 0;
    for(double i = 1; i<=num; i++)
        {
        sum = sum + GOD(i);
    }
    System.out.println((int)sum);
}
}

Answer 1

You should not be using doubles to perform integer arithmetic. Stick to int or long.

This is a brute-force search that follows the instructions very literally. That is the wrong approach. Similar to Project Euler Problem 3, the fast way to find the largest factor is by finding the smallest factors. Just divide by 2 as many times as possible.

Example:

$$360 = 2^3 \cdot 45$$

The largest odd divisor is therefore 45.

Answer 2

First some remarks to your code (in addition to what @200_success already said):

• Use more horizontal space and make the spacing consistent. if (num % i == 0 && i % 2 != 0) is better readable than if(num%2!=0).
• Fix the indentation.
• You don't need an else block after if (condition) { ... ; return; }.
• You have put the computation of the "greatest odd divisor" into a separate function GOD() which is good. The next step would be to compute the sum of odd divisors in a separate function. That keeps the main function short and allows you to add test cases easily.

About the performance: @200_success already made an excellent suggestion how to improve the determination of the greatest odd divisor. The suggested algorithm is probably the fastest for a single integer.

However, the programming challenge requires to compute C(1) + C(2) + C(3) + … + C(N) for large numbers N up to 10^9. Computing C(i) separately for each number and adding the values may not be fast enough for that challenge.

In that case you'll have to find a different algorithm, and I'll try to describe a possible approach.

First compute the result C(1) + C(2) + C(3) + … + C(N) for small values N = 1, 2, 3, …, that will give

1, 2, 5, 6, 11, 14, 21, 22, 31, 36, 47, 50, 63, 70, 85, …

If you are lucky then you'll "see" a pattern, and find some formula how to compute the numbers for arbitrary N quickly. If you don't find a pattern, then look up the sequence at the The On-Line Encyclopedia of Integer Sequences®. And indeed, it is listed as A135013. Even better, there is a PROG section with code snippets for different programming languages, e.g. for PARI/GP, a computer algebra system:

(PARI) a(n)=sum(k=1, log(n)\log(2)+1, round(n/2^k)^2) 

As you can see, there is a summation, but it is limited by log(N), not by N, which is a huge difference for large numbers!

Now translate that to Java – I don't want to spoil the fun of finding the final solution yourself! It should not be too difficult if you know that in PARI/GP, / is the "normal division", e.g. 6/4 = 3/2, and \ is the integer division with truncation, e.g. 6\4 = 1.

On my MacBook the resulting Java program computed the output for N = 10^9 in 0.157 sec.

Answer 3

        sum = sum + GOD(i);

In Java and most C-based languages, you can write this as

        sum += GOD(i);

Which is just a shorter way of writing the same thing. This works for most arithmetic operators.

import java.util.*;

You could just as well say

import java.util.Scanner;

As that is the only one that you actually use.

While some people like to save space by using the *, many (including me) prefer if all the imports are spelled out.