Subset Sum Mod N

14 April 2015

Problem overview

Get sum of value of all subsets (powersum) of int array a[] and return sum % mod

Example: "123" = [1, 2, 3] --> 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177. output: 123 % mod = X

using mod = 7 -> output = 123 % 7 = 3

Algorithm analysis

  1. generate all subsets of a
  2. compute sum of all elements generated

Code in Java

public static int getLuckyRemainder(String x, int mod) {



<span class="k">if</span> <span class="o">(</span><span class="n">x</span> <span class="o">==</span> <span class="kc">null</span> <span class="o">||</span> <span class="n">x</span><span class="o">.</span><span class="na">equals</span><span class="o">(</span><span class="s">""</span><span class="o">))</span> <span class="o">{</span>
    <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
<span class="o">}</span>

<span class="kt">char</span><span class="o">[]</span> <span class="n">ca</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="na">toCharArray</span><span class="o">();</span>
<span class="kt">int</span> <span class="n">a</span><span class="o">[]</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">x</span><span class="o">.</span><span class="na">length</span><span class="o">()];</span>
<span class="n">String</span> <span class="n">s</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>

<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">ca</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">s</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Character</span><span class="o">(</span><span class="n">ca</span><span class="o">[</span><span class="n">i</span><span class="o">]).</span><span class="na">toString</span><span class="o">();</span>
    <span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">parseInt</span><span class="o">(</span><span class="n">s</span><span class="o">);</span>
<span class="o">}</span>
<span class="n">List</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;&gt;</span> <span class="n">listOfSets</span> <span class="o">=</span> <span class="n">getAllSubsets</span><span class="o">(</span><span class="n">a</span><span class="o">);</span>

<span class="kt">int</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">listInt</span> <span class="o">:</span> <span class="n">listOfSets</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">for</span> <span class="o">(</span><span class="n">Integer</span> <span class="n">i</span> <span class="o">:</span> <span class="n">listInt</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">sum</span> <span class="o">+=</span> <span class="n">i</span><span class="o">;</span>
    <span class="o">}</span>
<span class="o">}</span>

<span class="k">return</span> <span class="n">sum</span> <span class="o">%</span> <span class="n">mod</span><span class="o">;</span>




}



public static List<List<Integer>> getAllSubsets(int a[]) {
    List<List<Integer>> result = new ArrayList<>();
    int n = a.length;
    int maxBin = new Double(Math.pow(2, n)).intValue();



<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">while</span> <span class="o">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">maxBin</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">list</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;&gt;();</span>

    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(((</span><span class="n">x</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="o">)</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="o">))</span> <span class="o">{</span>
            <span class="n">list</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">]);</span>
        <span class="o">}</span>
        <span class="n">j</span><span class="o">++;</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="o">;</span>
    <span class="o">}</span>
    <span class="n">result</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">list</span><span class="o">);</span>
    <span class="n">i</span><span class="o">++;</span>
<span class="o">}</span>

<span class="k">return</span> <span class="n">result</span><span class="o">;</span>




}

Full source code

comments powered by Disqus