Problem Statement ���� A sequence of integers (a1, a2, a3, ..., an) is called arithmetic if a2 - a1 = a3 - a2 = a4 - a3 = ... In order to make the given sequence arithmetic, you are allowed to replace each element with a different integer value (no fractions allowed). Unfortunately, each such replacement has an associated cost of 1. Return the minimum cost required to make the given sequence arithmetic. If the given sequence is already arithmetic, return 0. Definition ���� Class: ArithmeticReplace Method: howMany Parameters: int[] Returns: int Method signature: int howMany(int[] seq) (be sure your method is public) ����

Notes - An element can be replaced by a value less than -10000 or greater than 10000. Constraints - seq will contain between 3 and 50 elements inclusive. - Each element of seq will be between -10000 and 10000 inclusive. Examples 0)

���� {1,4,7,11} Returns: 1 Replacing the 11 with a 10 we get an arithmetic sequence. 1)

���� {-10,-5,0,5,10,15} Returns: 0 This sequence is already arithmetic. 2)

���� {157, 119, 15, -5, -25} Returns: 2 Replacing the first two elements with 55 and 35 we get an arithmetic sequence. 3)

we add solutions... can anybody make it further correct... coz we are able to find out the correct result by adding further code to that but that doesn't make the series in AP

see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...

Arrays.sort(seq); System.out.println("length " + seq.length); for (int i = 0; i < seq.length; i++) System.out.print(seq[i] + " "); int dif = 0; System.out.println("diff " + dif); int[] a = new int[seq.length - 1]; for (int i = 0; i < seq.length - 1; i++) { // System.out.println("each diff " + (seq[i + 1] - seq[i])); a[i] = seq[i + 1] - seq[i]; System.out.print(" " + a[i]); } System.out.println(); System.out.println("a length " + a.length); Arrays.sort(a); for (int i = 0; i < a.length; i++) System.out.print(" " + a[i]);

int n = 1, k = 1, l = 0; for (int i = 0; i < a.length - 1; i++) { if (a[i + 1] == a[i]) { n++; l = a[i]; } else { if (n > k) { k = n; l = a[i]; }

n = 1; }

} System.out.println(); System.out.println("l " + l); System.out.println("k " + k); dif = l; // seq.length-k*2; for (int i = 0; i < seq.length - 1; i++) { if (seq[i + 1] - seq[i] != dif) { counter++; } } // if (counter > 0) // counter++; return counter; }

/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub

ArithmeticReplace ar = new ArithmeticReplace(); int k = ar.howMany(new int[] {1,100,10,40,2,200,-71,250,99,103,325}); System.out.println("k>>>> " + k); }

}

-----------------------

thanks

[ April 09, 2006: Message edited by: amit taneja ] [ April 10, 2006: Message edited by: amit taneja ]

see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...

How can you find an anwer, which is not making the series in AP?

amit taneja
Ranch Hand

Joined: Mar 14, 2003
Posts: 810

posted

0

the orginal problem is within the ================== lines in first post of this thread...

please read carefully and then try to understand what the question is saying ...

So, rather than answering Ryan's question, you simply tried to delete the evidence? No good - we remember what it said earlier. You've asked several past questions from Google CodeJam problem sets which violated their copyright. Why not be honest about where this stuff comes from? If it's from one of their old problem sets, post a link to where it can be viewed. If it's from a new (current) problem set, then please don't post at all.

[amit]: see the question is asking that find out how many numbers we should add to make the series to be in AP

No, it asks how many numbers you should replace. You can make any sequence arithmetic if you replace enough numbers; the trick is to find the minimum required.

"I'm not back." - Bill Harding, Twister

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1030

4

posted

0

I had to write the program just so I could see how they came up with 7 for the last example. Oh, I see now... the difference between consecutive terms is 25, starting at 75. So 100, 200, 250 and 325 stay, while the rest get replaced.

(Besides I needed an excuse to used my Mixed class for fractional numbers again. )

I have one algorithm. Has anyone else figure this out yet?

When I looked at this earlier, I had a trivial but very inelegant solution (looking at all pairs of two elements, if the delta is valid - expand a new arrar and save the array that had the fewest replacements).

Ryan and Steve: yeah, I had made a quick solution similar to what Steve describes. There are various optimizations that can be made along the way, but it's still fundamentally an O(n^3) algorithm as far as I can tell. I don't think it's quite as inelegant or trivial as stave makes it sound, but it does feel like there ought to be some more clever solution possible. There's a certain temptation to apply an FFT or something to try to find the strongest underlying patterns more quickly. Which is probably overkill, but oh well. More to the point, I don't think it would actually work. But there's a lingering feeling that something similar might. Unfortunately, I don't see a specific avenue to pursue. So for now, I'll content myself with O(n^3), I guess.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1030

4

posted

0

Rather than figuring out all the values in the modified sequence, I just figure out the slope and y-intercept implied by each pair of points. If the slope is an integer (i.e. differenceBetweenTwoValues % distanceBetweenThem == 0) then I save that slope/intercept pair. The slope/intercept pair that's used between the most pairs is the one that would be used for the "repaired" sequence (if I bother to figure it out).

For example... Original sequence: {20,24,29,32} slope=4, intercept=20 is used between 3 pairs: 20-24, 24-32, and 20-32. slope=non-integer between 20-29, so ignore it. slope=5, intercept=19 is used between 1 pair : 24-29 slope=3, intercept=23 is used between 1 pair : 29-32

Since (4, 20) is the most popular pair, it would be used for the final sequence.

BUT... I don't even need to figure out what the new sequence is. Rather than comparing old values and new values, I can determine how many values would have to change with the following equation:

where "Pairs" is the number of pairs in the original sequence that used the most popular slope/intercept pair (3 in the example above).

Let's see... 8*3 = 24. 24+1 = 25. sqrt(25) = 5. 5+1=6. 6/2=3. 4-3=1. So the return value is 1. (I love the quadratic equation.)

Since I don't calculate the whole new sequence implied by each pair, my alg is only O(n^2). [ April 20, 2006: Message edited by: Ryan McGuire ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Ah, nicely done. I had started down a similar route, but I was considering only slopes, not intercepts. When I saw this was insufficient, I jumped to considering all points, when I should have considered slope plus intercept. Seems obvious in retrospect.

The one advantage I can see for my solution is that it doesn't require any substantial memory or other storage, as I don't need to keep cumulative counts for a bunch of different slope/intercept pairs. In most cases this is a minor issue, as memory is cheap. But since the memory usage in your solution is O(n^2) (right?), in some situations it may be necessary to switch to a less memory-intensive algorithm. Though of course you could also use a database of some sort instead, ultimately relying on some file-based storage I assume.