How to place random operator(ex.+ or -) in front of digit?

Question

I want to know the smallest number answering the sum problem *1*2*3*4...*n = k (* indicates + or -). For example:

for k = 0: +1+2-3 = 0, so, the smallest answer is 3.
for k = 4: -1+2+3 = 4, so the smallest answer is 3.

for k = 12: -1+2+3+4+5+6-7 = 12, so the smallest answer is 7. // 4 = -1+2+3

// 5 = +1-2-3+4-5
// 6 = +1+2+3

// 7 = -1+2-3+4+5
// 8 = -1+2+3+4
// 9 = -1-2+3+4+5

// 10 = +1+2+3+4
// 11 = +1-2+3+4+5

// 12 = -1+2+3+4+5+6-7
// 13 = -1+2-3+4+5+6
// 14 = -1+2+3+4+5

Is there any algorithm to do this?

import java.util.Random;
import java.util.Scanner;

public class EX_03 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int Case = sc.nextInt();
        int arr[] = new int[Case];
        int sum[] = new int[Case];
        int k = 0;
        int count = 0;

        for (int i = 0; i < Case; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < Case; i++) {
            while (true) {
                ++k;
                if(count==0){
                sum[i] += k;
                count++;}
                else{
                    sum[i] -= k;
                }
                if(sum[i] == arr[i]) break;

            }
        }
        // 0 = +1+2-3
                // 1 = +1
                // 2 = +1-2+3
                // 3 = +1+2

        // 4 = -1+2+3

        // 5 = +1-2-3+4-5
        // 6 = +1+2+3

        // 7 = -1+2-3+4+5
        // 8 = -1+2+3+4
        // 9 = -1-2+3+4+5

        // 10 = +1+2+3+4
        // 11 = +1-2+3+4+5

        // 12 = -1+2+3+4+5+6-7
        // 13 = -1+2-3+4+5+6
        // 14 = -1+2+3+4+5

        // 15 = 123456

        /*
         * Random operatorChoice = new Random(); int operator =
         * operatorChoice.nextInt(2);
         * 
         * while (k >= 0) { ++k; for (int i = 0; i < Case; i++) { switch
         * (operator) { case 0: sum[i] += k; break; case 1: sum[i] -= k; break;
         * default: break; } if(sum[i] == arr[i]) break; else continue; } }
         */

        for (int i = 0; i < Case; i++) {
            System.out.println(k);
        }

    }

}

Example input:

12 -3646397

Expected output for that input:

7 2701

Maybe I get you wrong completely, but your title doesn't seem to match to your question — Ole Albers, Oct 11 '16 at 07:23
Hint: changing the sign of one of the numbers always changes the sum by an even amount — samgak, Oct 11 '16 at 07:27
@J.Doe You got a hint from samgak; does that help? If no, you can describe what you did with that hint, and then people will see where exactly you had problems. You have to show exactly where you are stuck, otherwise it's hard to judge what is an answer and what is not. — anatolyg, Oct 11 '16 at 07:49
actually, i can't think some idea. if any body show some code, i will take then — J.Doe, Oct 11 '16 at 07:53
This problem is a good candidate for a [recursive solution](https://stackoverflow.com/questions/717725/understanding-recursion). — user5226582, Oct 11 '16 at 08:38
Please read the link about recursion. It's very interesting and is not overly complicated. We don't wan't to steal learning opportunities from you. Once you understand recursion, and have a go at it, we might be able to help with more specific questions if you have further problems. — user5226582, Oct 11 '16 at 09:02
thanks! yet, i want to solve that question. i have a problem that thinking about many case about that question. so please show some code about your think — J.Doe, Oct 11 '16 at 09:06

score 2 · Answer 1 · answered Oct 11 '16 at 08:00

Use this idea (suggested by samgak):

changing the sign of one of the numbers always changes the sum by an even amount

So, how many numbers do you need to get a sum of 9? It must be an odd number (*1*2*3 or *1*2*3*4*5 or *1*2*3*4*5*6*7 or ...) - this is the first thing you need to notice.

Then, consider a maximal sum:

+1+2+3+...+n

It's easy to calculate this sum (I forgot the answer, but it's easy).

Then (this is the most important step), try changing signs and examine what happens to the sum:

+1+2+3+4+5 = 10
-1+2+3+4+5 = ? (the sum is smaller by an even number)
+1-2+3+4+5 = ? (the sum is smaller by another even number)
+1+2-3+4+5 = ? (the sum is smaller by another even number)
+1+2+3-4+5 = ? (the sum is smaller by another even number)
+1+2+3+4-5 = ? (the sum is smaller by another even number)

From here, making an algorithm is easy. Keep in mind that you really don't need to print the expression (sum) itself, only prove that it exists. So no need to find where exactly your target number appears in the above list, just to find the length of that list.

Thanks a lot anatolyg. but i don't under stand "changing the sign of one of the numbers always changes the sum by an even amount" and i can't speak english very well... so, if you show some code, i will read that! — J.Doe, Oct 11 '16 at 08:10
I think the third part of my answer (the one with the question-marks) is what you need. Try to calculate the sums (replace the question-mark with a number) and you will understand what I wanted to say. — anatolyg, Oct 11 '16 at 08:27
Note: I don't want to provide code because the question requests an algorithm, not code. The question is more useful and more interesting that way - code would require many comments and a description of the algorithm anyway. — anatolyg, Oct 11 '16 at 08:29

score 0 · Accepted Answer · answered Oct 11 '16 at 09:07

You can try and improve that code which use recursivity

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 *
 * @author Aroniaina
 */
public class RandomOperator {

    public static HashMap<Integer, List<Integer>> possibilities(Integer current) {
        //Return -1 and 1 if current si equal to 1
        if (current == 1) {
            HashMap<Integer, List<Integer>> result = new HashMap<>();
            //Add positive possibility
            List<Integer> list1 = new ArrayList<>();
            list1.add(current);
            result.put(current, list1);
            //Add negative possibility
            List<Integer> list2 = new ArrayList<>();
            list2.add(-1 * current);
            result.put(-1 * current, list2);
            return result;
        } else {
            HashMap<Integer, List<Integer>> previous = possibilities(current - 1);
            HashMap<Integer, List<Integer>> temp = new HashMap<>();
            temp.putAll(previous);
            for (Integer prev : previous.keySet()) {
                if (previous.get(prev).size() == (current - 1)) {
                    //Add positive possibility                
                    List<Integer> list1 = new ArrayList<>();
                    list1.addAll(previous.get(prev));
                    list1.add(current);
                    temp.put(current + prev, list1);
                    //Add negative possibility
                    List<Integer> list2 = new ArrayList<>();
                    list2.addAll(previous.get(prev));
                    list2.add(-1 * current);
                    temp.put(-1 * current + prev, list2);
                }
            }
            return temp;
        }
    }

    public static void main(String args[]) {
        for (int i = 0; i < 20; i++) {
            Integer toVerify = i;
            int current = 1;
            while (true) {
                HashMap<Integer, List<Integer>> result = possibilities(current);
                if (result.keySet().contains(toVerify)) {
                    System.out.print(toVerify + " = ");
                    for (Integer e : result.get(toVerify)) {
                        System.out.print(e > 0 ? ("+" + e) : (e));
                    }
                    break;
                }
                current++;
            }
            System.out.println("");
        }
    }
}

OUTPUT :

0 = -1-2+3
1 = +1
2 = +1-2+3
3 = +1+2
4 = -1+2+3
5 = +1+2+3+4-5
6 = +1+2+3
7 = -1+2-3+4+5
8 = -1+2+3+4
9 = -1-2+3+4+5
10 = +1+2+3+4
11 = +1-2+3+4+5
12 = -1+2+3+4+5+6-7
13 = -1+2+3+4+5
14 = +1+2+3+4+5+6-7
15 = +1+2+3+4+5
16 = +1+2+3+4+5-6+7
17 = +1-2+3+4+5+6
18 = +1+2+3+4-5+6+7
19 = -1+2+3+4+5+6

wow... thanks man. you are best programmer. i can learn that code many thing. and i will study furthermore. thanks a lot your code. — J.Doe, Oct 11 '16 at 09:10

How to place random operator(ex.+ or -) in front of digit?

2 Answers2